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

递归实现指数型枚举

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

相关推荐

09-11 03:07
已编辑
湖南大学 Java
Lemon2ee:上海,nlp,985,博士,哪怕少一个我都觉得这是假的
点赞 评论 收藏
分享
牛客263158796号:我领羊一面后十天不挂也不推进 今天问hr说等前序的第一批意向发完看情况再看是否推进
点赞 评论 收藏
分享
1 收藏 评论
分享
牛客网
牛客企业服务