AcWing 93. 递归实现组合型枚举
原题链接
简单
作者:
xwx_9
,
2024-03-29 21:21:17
,
所有人可见
,
阅读 1
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
//94排列 93组合 递归->树 组合要考虑消除重复出现的元素 即在递归时添加限制条件
//限制条件-> 例如:(从小到大) or (从大到小)本题要求按照字典序 即 从小到大
using namespace std;
const int N=26;
int n,m;
int arr[N];
void dfs(int u,int start){
//剪枝优化
//当前选的第几位数:(u-1)
//从当前位置出发能选的元素(n-start+1)->start选到n
//如果当前位置加上剩余能选的元素小于m,代表当前分支没有可选择的方案
if(u+n-start<m)return;
//边界条件 输出
if(u==m+1){
for(int i=1;i<=m;i++){
printf("%d ",arr[i]);
}
puts("");
return;
}
for(int i=start;i<=n;i++){
arr[u]=i;
dfs(u+1,i+1);
//arr[u]=0;回溯
}
}
int main(){
scanf("%d%d",&n,&m);
dfs(1,1);
return 0;
}