《算法竞赛进阶指南》 93. 递归实现组合型枚举

本文主要是介绍《算法竞赛进阶指南》 93. 递归实现组合型枚举，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

• 是否看了题解找思路

1.问题分析

简单的dfs，但是题解中用数组的0号位置存放数组的长度第一次见。

核心代码：

for (int i=x;i<=n;i++){p[++p[0]]=i;dfs(i+1);p[p[0]--]=0;}

其实稍加思索，本题就可以用二进制位运算来存储状态。
核心代码(不是自己写的)：

void dfs(int x,int now,int date)
{if (x>n || date+(n-x+1)<m)return ;if (date==m){for (int i=1;i<=n;i++)if (now>>(i-1) & 1)cout<<i<<" ";puts("");return ;}dfs(x+1,now+(1<<x),date+1);dfs(x+1,now,date);
}

2.具体代码

#include <iostream>using namespace std;
int n,m,p[100];
void dfs(int x)
{if(p[0]==m)//p[0]存的是长度{for(int j=1;j<=p[0];j++)    cout<<p[j]<<" ";cout<<endl;}else{for(int i=x;i<=n;i++){p[++p[0]]=i;dfs(i+1);p[0]--;}}
}
int main()
{cin>>n>>m;dfs(1);return 0;
}

3.总结

天天天天划水划水

这篇关于《算法竞赛进阶指南》 93. 递归实现组合型枚举的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---