c - 如何用C语言递归获取给定数量元素的集合的子集？

Question

例如，当用户输入 4 和 2 时，表示原始集合有 4 个元素:(1,2,3,4)，子集应有 2 个元素。我找到了一种使用下面的代码以常规形式呈现这些子集的方法，例如 (1,2)(1,3)(1,4)(2,3)(2,4)(3,4) ，但是我的作业需要类似二进制的形式，例如 (1,2) 应该是 (1,1,0,0) 和 (2,4) 应该是 (0,1,0,1) 等。在 (1,1,0 ,0)，第一个二进制1表示原始集合(1,2,3,4)中第一个为1的元素包含在子集中。第二个二进制1表示原始集合中的第二个元素2包含在子集中。而第三个和第四个数字3和4则不是。例如，集合 (1,2,3,4,5) 中的子集 (1,2,5) 可以表示为 (1,1,0,0,1)

void subset(int n, int k, int B[], int q, int r) {
    if (q == k) {
        for (int i = 0; i < k; i++) {
            printf("%d ", B[i]);
        }
        printf("\n");
    } else {
        for (int i = r; i < n; i++) {
            B[q] = i+1;
            subset(n, k, B, q+1, i+1);
        }
    }
}

在main中(n是原始集合中的元素数量，k是子集中的元素数量):

int B[101];
subset(n, k, B, 0, 0);

我的作业还需要这个带有 4 个精确参数的递归函数( i 来自 (1,2,3,4...i) ):

void subsets(int B[], int n, int k, int i)

我尝试了很多方法都失败了。如果有人能帮助我，我将不胜感激，谢谢。

更新: 感谢rajender kumar，使用下面的代码解决了类似二进制的输出问题:

void printSubsets(int B[], int n, int k, int q, int i) {
    if (q == k) {
        int finalArry[MAX_SIZE+1] = {0};
        for (int i = 0; i < k; i++) {
            finalArry[B[i]] = 1;
        }
        printSet(finalArry, n);

    } else {
        for (int j = i; j < n; j++) {
            B[q] = j+1;
            printSubsets(B, n, k, q+1, j+1);
        }
    }
}

但我仍然需要从 int q 或 int i 中删除一个参数。

Answer 1

这应该可以完成工作:

void subset(int n, int k, int B[], int i) {
    if (k == 0) {
        for (int d = 0; d < n; d++) {
            printf("%d ", B[d]);
        }
        printf("\n");
    } else if (i >= n || k > n - i) {
        return;
    } else {
        B[i] = 1;
        subset(n, k - 1, B, i + 1);
        B[i] = 0;
        subset(n, k, B, i + 1);
    }
}

int main(int argc, char **argv) {
    int n, k;
    int B[4];

    memset(B, 0, sizeof(B));
    n = sizeof(B) / sizeof(B[0]);
    k = 2;
    printf("n=%d\nk=%d\n", n, k);
    subset(n, k, B, 0);
    return 0;
}