AcWing 93. 递归实现组合型枚举
原题链接
简单
作者:
ofs
,
2024-04-11 23:42:56
,
所有人可见
,
阅读 2
#include<iostream>
#include<cstdio>
using namespace std;
int n,m;
const int N=30;//适当扩大范围
int way[N];//存储第n位的数据,第i位选了哪个数
void dfs(int u,int start)//此时该选第u位的数,数字可以从start-n之间选择
{
//剪枝,也就是优化
//提前筛选出不符合条件的数据,直接跳过,节省时间
if(u+n-start<m) return;//此时表示后面剩的数不够填满所有位置
if(u>m)//所有选择结束,输出最终结果
{
for(int i=1;i<=m;i++)
printf("%d ",way[i]);
puts("");//换行
return;
}
for(int i=start;i<=n;i++)//start位限制大小关系,保证升序排列,防止重复
{
way[u]=i;//此位置选择i
dfs(u+1,i+1);//执行下一个位置,从i+1数字开始选择
way[u]=0;//恢复现场,保证子节点选择的公平性
}
}
int main()
{
cin>>n>>m;
dfs(1,1);
return 0;
}