使用位掩码递归生成n元集合k元子集的C++代码调试问题

你遇到的问题核心是递归过程中缺少回溯操作，咱们来拆解下原因和解决办法：

你的原始代码里，当在循环中把arr[i] = 1并发起递归调用后，没有将这个位置的状态恢复为0。这就导致递归返回后，该位置的1会被保留，后续的循环迭代会在已经存在多个1的数组上继续操作，最终输出全是1的错误结果。

修正思路 #

在递归调用返回后，必须执行回溯操作：把刚才设为1的位置重新置为0。这样下一次循环迭代时，数组会回到当前层级的初始状态，才能正确生成不同的子集组合。

修正后的完整代码 #

#include <iostream>
using namespace std;
void combinations(int *, int, int, int,int c);
int main() {
    int n = 5;
    int k = 3;
    int bitMask[5] = {0};
    combinations(bitMask,0,n,k,0);
}
void combinations(int* arr, int start, int n, int k,int c) {
    if(c == k) { // 这里改成参数k更通用，不用硬编码3
        for(int i = 0; i < n; i++) {
            cout<<arr[i];
        }
        cout<<endl;
    }else {
        for(int i = start; i < n; i++) {
            arr[i] = 1;
            combinations(arr,i+1,n,k,c+1);
            arr[i] = 0; // 关键回溯步骤：恢复当前位置的初始状态
        }
    }
}

为什么这行代码有效？ #

当递归调用combinations(arr,i+1,n,k,c+1)执行完成并返回后，将arr[i]设回0，就能保证下一次循环（i递增后），数组是干净的初始状态，不会带着上一次递归留下的1继续生成组合。这样就能正确遍历所有k个1的不同位置组合，得到你想要的输出：

11100
11010
11001
10110
10101
01110
01101
01011
00111

额外提个小建议：把if(c==3)里的3改成参数k，这样代码不用修改数值就能适配不同的k值，通用性更强~

内容的提问来源于stack exchange，提问作者Petar Vitanov