coding笔记：递归实现指数型枚举

92. 递归实现指数型枚举

从 1∼n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。

思路1—二进制表示

既然这n个数每一个数既可以选也可以不选，我们就可以用二进制表示来表示每一位选（1）或是不选（0）。

代码实现

void solu_92_no_rec(){
    int n;
    cin>>n;
    for(int i=0;i<1<<n;i++){
        for(int j=1;j<=n;j++){
            if(i>>(n-j)&1) printf("%d ",j);
        }
        puts("");
    }
}

思路2—递归

使用深度优先搜索，对每个位置选或是不选进行遍历，递归搜索树如下图：

代码实现

vector<int> vec;
void dfs(int n,int l){
    if(l==n){
        for(auto i : vec){
            printf("%d ",i);
        }
        puts("");
        return;
    }
    //select l;
    vec.push_back(l+1);
    dfs(n,l+1);
    vec.pop_back();
    //no select
    dfs(n,l+1);
}
void solu_92_with_rec(){
    int n;
    cin>>n;
    dfs(n,0);
}