题解 | #递归实现指数型枚举#
递归实现指数型枚举
https://ac.nowcoder.com/acm/problem/50911
#思路: 状态压缩
由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;
}