AcWing93. 递归实现组合型枚举：输出从1~n中随机选出的m个整数

题目

从 1∼$n$ 这 $n$ 个整数中随机选出 $m$ 个，输出所有可能的选择方案。

输入格式

两个整数 $n,m,$ 在同一行用空格隔开。

输出格式

按照从小到大的顺序输出所有方案，每行 1 个。

首先，同一行内的数升序排列，相邻两个数用一个空格隔开。

其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如 1 3 5 7 排在 1 3 6 8 前面）。

数据范围

$n>0$,
$0\le m\le n$,
$n+(n-m)\le 25$

输入样例

5 3

输出样例

1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5 

思考题：如果要求使用非递归方法，该怎么做呢？

思路

思路类似于AcWing92，但是多了一个个数限制。

另外，因为升序排列，所以可以枚举每个数，就可以形成一棵递归搜索树。可以枚举当前在哪层，以及当前以哪个数开始继续往下搜。

代码

#include <bits/stdc++.h>
#include <vector>
using namespace std;vector<int> chosen; //被选择的数void print_subset(int n, int m, int x) {//剪枝：无解的情况//选择超过了m个，或即使再选上剩余的所有数也不够m个，则无解//这条剪枝保证一旦进入无解的分支就会立刻返回if (chosen.size() > m || chosen.size() + (n - x + 1) < m) {return ;}if (x == n + 1) {for (int i = 0; i < chosen.size(); i++) {printf("%d ", chosen[i]);}printf("\n");return ;}//“选num” 分支chosen.emplace_back(x);//记录num已被选择print_subset(n, m, x + 1); 求解子问题chosen.pop_back(); ///回溯到上一问题之前，还原现场//“不选num” 分支print_subset(n, m, x + 1);}int main() {int n, m;scanf("%d%d", &n, &m);print_subset(n, m, 1);return 0;
}

因为剪枝，时间复杂度从 $2^n$ 降低为 $C_n^m$。

递归搜索树写法：

#include <cstdio>
using namespace std;const int N = 30;
int path[N]; //存储路径（选择的数）
int n, m;void dfs(int u, int start) { //u当前层数，start当前在哪个数 if (u > m) { //已经找到了m个数for (int i = 1; i <= m; i++) {printf("%d ", path[i]);}puts("");} else {for (int i = start;  i <= n; i++) {path[u] = i; //当前层选择的数是idfs(u + 1, i + 1);path[u] = 0; //恢复现场}}
}int main() {scanf("%d%d", &n, &m);dfs(1, 1);return 0;
}