信息学奥赛一本通-1317例5.2组合的输出-洛谷-P1157-组合的输出
目录
信息学奥赛一本通 1317：【例5.2】组合的输出 | 洛谷 P1157 组合的输出
【题目链接】
【题目考点】
1. 深搜回溯
【解题思路】
解法1：深搜回溯
组合与排列的区别为，组合是一个数字集合，是没有顺序的。
对于排列来说，1 2 3与1 3 2是两种排列。对于组合来说，1 2 3与1 3 2是同一种组合。
如果按搜索全排列的方法来进行搜索，数字相同但顺序不同的情况会多次出现，而我们只需要统计其中的一次。
在相同数字的多种排列中，升序排列一定是唯一的，因而升序排列与组合一定是一一对应的。（例如3 2 1三个数字的升序排列为1 2 3），这里我们就搜索多种排列中的升序排列输出，即可满足题目中“将每个组合按升序顺序输出”的要求。
要保证搜索到的是升序序列，具体写法有两种
- 写法1：当前搜索到的数字要大于等于已经保存的升序排列的最后一个数字
- 写法2：递归时传入遍历的起始值。由于整个序列是由1~n构成的，只要传入搜索的起始值，后面取到的数字一定与之前取到的数字不同，可以不需要记录数字是否出现过，即不设vis数组。
【题解代码】
解法1：深搜回溯
#include<bits/stdc++.h>
using namespace std;
int nums[25];//记录要输出哪些数，记录在num[1],num[2]...,num[r]
int n, r;//从n个元素中抽出r个元素
void dfs(int k, int st)//k:要确定升序排列中的第几个数，要填入的数字大于等于st
{
if(k > r)//如果已经填充了r个数字，再看第r+1个数字
{//输出存在num中的排列数
for(int j = 1; j <= r; ++j)
cout << setw(3) << nums[j];
cout << endl;
return;
}
for(int i = st; i <= n; ++i)
{
nums[k] = i;//添加数字
dfs(k+1, i+1);
}
}
int main()
{
cin >> n >> r;
dfs(1, 1);
return 0;
}