通州广州网站建设,营销百度app下载手机版,中国最大的小程序公司,做网站有未来吗题目
从 1∼ n n n 这 n n n 个整数中随机选出 m m m 个#xff0c;输出所有可能的选择方案。
输入格式
两个整数 n , m , n,m, n,m, 在同一行用空格隔开。
输出格式
按照从小到大的顺序输出所有方案#xff0c;每行 1 个。
首先#xff0c;同一行内的数升序排列输出所有可能的选择方案。
输入格式
两个整数 n , m , n,m, n,m, 在同一行用空格隔开。
输出格式
按照从小到大的顺序输出所有方案每行 1 个。
首先同一行内的数升序排列相邻两个数用一个空格隔开。
其次对于两个不同的行对应下标的数一一比较字典序较小的排在前面例如 1 3 5 7 排在 1 3 6 8 前面。
数据范围 n 0 n0 n0, 0 ≤ m ≤ n 0≤m≤n 0≤m≤n, n ( n − m ) ≤ 25 n(n−m)≤25 n(n−m)≤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;vectorint 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 2^n 2n 降低为 C n m C_n^m Cnm。
递归搜索树写法
#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;
}
