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

递归实现指数型枚举

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;
}
全部评论

相关推荐

11-05 07:29
贵州大学 Java
点赞 评论 收藏
分享
10-28 14:42
门头沟学院 Java
watermelon1124:因为嵌入式炸了
点赞 评论 收藏
分享
评论
1
收藏
分享
牛客网
牛客企业服务