输出全部组合的问题

给定一个字符串S，其中S中的字符互不相同，输出S中字符的所有组合，
如S = "abc"， 则输出：空，a, b, c, ab, ac, bc, abc,

下面是实现的程序：

void fullCombination(char *arr)
{
    int len = strlen(arr);
    int *mask = new int[len];
    int i, j;

    for(mask[0]=1, i=1; i<len; i++)
        mask[i] = (mask[i-1]<<1);

    int max = (1 << len);
    int temp;
    for(int count=0; count < max; count++) {
        printf("[");
        temp = count;
        for(j=0; temp!=0; j++) {
            if(temp & mask[j]) {
                printf("%c", arr[j]);
                temp ^= mask[j];
            }
        }
        printf("]\n");
    }
}

void testFullCombin()
{
    fullCombination("abcdef");
}

上面是非递归的实现方法。

递归的实现方法：

void innerCombin(const char *arr, int n, int idx, int count, char *buf)
{
    if(count == n) {
        printf("%s\n", buf);
        return;
    }
    if (arr[idx] == '\0') return;
    buf[count] = arr[idx];
    innerCombin(arr, n, idx+1, count+1, buf);
    innerCombin(arr, n, idx+1, count, buf);
}
void combination(const char *arr, int n)
{
    if (arr==NULL) return;
    if (strlen(arr) < n) return;
    char *buf = new char[n+1];
    buf[n] = '\0';
    innerCombin(arr, n, 0, 0, buf);
    delete [] buf;
}

void testCombin()
{
    char arr[27] = "abcdefghijklmnopqrstuv";
    strcpy(arr, "abcde");
    int len = strlen(arr);
    for(int i=1; i<=len; i++) {
        combination(arr, i);
    }
}

更简单的一种递归办法：

void innerCombin2(char *arr, int idx, int count, char *buf)
{
    if(arr[idx] == '\0') {
        buf[count] = '\0';
        printf("%s\n", buf);
        return;
    }
    innerCombin2(arr, idx+1, count, buf);
    buf[count] = arr[idx];
    innerCombin2(arr, idx+1, count+1, buf);
}
void combination2(char *arr) {
    if(arr == NULL) return;
    char *buf = new char[strlen(arr) + 1];
    innerCombin2(arr, 0, 0, buf);
}
void testCombin2()
{
    combination2("abcde");
}