AcWing 93. 递归实现组合型枚举
原题链接
简单
作者:
骄骄是骄傲的骄骄
,
2022-02-15 20:48:17
,
所有人可见
,
阅读 196
/*
在 1-n 中选取 m 个
那么对于 1-n 中的某个数
只存在 选 或 不选 两种情况
边界情况:
最后一个数已经选取 且 选取的数刚好 m 个
剪枝情况:
当前选取的数超过 m 个
剩下的数 + 当前选取的数 < m
*/
#include <iostream>
using namespace std;
int n, m;
int used[20]; // 记录数字的使用情况
// 我们用used[0]记录当前使用了多少个数
// 当前数
void dfs(int u){
// 剪枝
if(used[0]>m || n-(u-1)+used[0]<m)
return ;
// 边界情况
// 实际上我们不用判断数量是否是 m 个
// 因为剪枝时已经灭掉了 !m 的情况
if(u>n && used[0]==m){
for(int i=1; i<=n; i++)
if(used[i]) printf("%d ", i);
puts("");
}
// 每个数有两种状态
// 选
used[u]=1;
used[0]++;
dfs(u+1);
used[u]=0;
used[0]--; // 恢复现场
// 不选
dfs(u+1);
}
int main(){
cin>>n>>m;
dfs(1);
return 0;
}