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