题解 | #递归实现指数型枚举#

#思路： 状态压缩

由Cn0+Cn1+Cn2+Cn3+....+Cnn=2^n。我们能确定要输出多少次。 用1表示选了哪个数，用0表示未选，可以发现选取排列可以2进制表示。 如：当n=2时；

I. 00 表示都不选。

II. 01 表示选1。

III.10 表示选2.

IV. 11 表示选1和2。

好了，我们现在已经知道如何表示了，接下来用递归来模拟：

#include<bits/stdc++.h>
using namespace std;
int N;

void dfs(int n)
{
    if(n==(1<<N))return;
    int res=n;
    int ans=1;
    while(res)
    {
        if(res&1)cout<<ans<<' ';
        ans++;
        res>>=1;
    }
    cout<<endl;
    dfs(n+1);//用于枚举各种组合
}

int main(void)
{
    cin>>N;
    dfs(0);//从0开始，总和为2^n(包括啥都不选的情况)
    return 0;
}