【题目来源】
洛谷：P1157 组合的输出 - 洛谷 (luogu.com.cn)
【题目描述】
排列与组合是常用的数学方法，其中组合就是从 \(n\) 个元素中抽出 \(r\) 个元素（不分顺序且 \(r\le n\)），我们可以简单地将 \(n\) 个元素理解为自然数 \(1,2,\dots,n\)，从中任取 \(r\) 个数。
现要求你输出所有组合。
例如 \(n=5,r=3\)，所有组合为：
\(123,124,125,134,135,145,234,235,245,345\)。
【输入】
一行两个自然数 \(n,r(1\lt n\lt 21,0\le r\le n)\)。
【输出】
所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。
注意哦！输出时，每个数字需要 \(3\) 个场宽。以 C++ 为例，你可以使用下列代码：
cout << setw(3) << x;
输出占 \(3\) 个场宽的数 \(x\)。注意你需要头文件 iomanip。
【输入样例】
5 3
【输出样例】
1 2 31 2 41 2 51 3 41 3 51 4 52 3 42 3 52 4 53 4 5
【解题思路】
【算法标签】
《洛谷 P1157 组合的输出》 #搜索# #递归# #排列组合#
【代码详解】
#include <bits/stdc++.h>
using namespace std;int n, k, b[25] = {0}; // 定义全局变量：n-总数，k-选择数，b-标记数组// 输出当前组合
void shuchu() {for (int i = 1; i <= n; i++) {if (b[i]) cout << setw(3) << i; // 输出被选中的数字，宽度为3}cout << endl; // 换行
}// 递归生成组合
void f(int flag, int num) {// flag: 当前起始位置// num: 剩余需要选择的数字个数// 终止条件：已选够k个数字if (num == 0) {shuchu(); // 输出当前组合return;}// 剪枝：剩余数字不足以选够k个if (n - flag + 1 < num) return;// 递归枚举所有可能的组合for (int i = flag; i <= n; i++) {b[i] = 1; // 选择当前数字f(i + 1, num - 1); // 递归处理后续数字b[i] = 0; // 回溯，取消选择}
}int main() {cin >> n >> k; // 输入总数n和选择数kf(1, k); // 从第1个位置开始，选择k个数字return 0;
}
#include <bits/stdc++.h>
using namespace std;int n, r, a[10]; // 定义全局变量：n-总数，r-选择数，a-存储当前组合// 深度优先搜索生成组合
void dfs(int step, int num) {// step: 当前选择的第几个数字（从1到r）// num: 当前可选的起始数字（保证组合有序避免重复）// 终止条件：已选够r个数字if (step > r) {// 输出当前组合（每个数字占5位宽度）for (int i = 1; i <= r; i++) {cout << setw(5) << a[i];}cout << endl;return;}// 枚举所有可能的数字（从num到n）for (int i = num; i <= n; i++) {a[step] = i; // 选择当前数字dfs(step + 1, i + 1); // 递归选择下一个数字（保证升序）a[step] = 0; // 回溯（可省略，因为会被覆盖）}
}int main() {cin >> n >> r; // 输入总数n和选择数rdfs(1, 1); // 从第1个位置开始，起始数字为1return 0;
}
【运行结果】
5 31 2 31 2 41 2 51 3 41 3 51 4 52 3 42 3 52 4 53 4 5