【题目描述】
排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素(不分顺序且r≤n)，我们可以简单地将n个元素理解为自然数1，2，…，n，从中任取r个数。现要求你用递归的方法输出所有组合。例如n＝5，r＝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
【输入描述】
一行两个自然数n、r(1<n<21，1≤r≤n)。
【输出描述】
所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。
【样例输入】
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【分析】
(1)是一道搜索回溯的题目，加上了选数的部分。
(2)两种框架都可以选择，选过的数不能再使用。
【参考代码1】
#include<bits/stdc++.h>
using namespace std;
int n,r; //定义一共几个数，需要选几个数
int pd[100],ans[100];//pd数组是判断是否用过这个数，ans是结果数组
void print() { //输出函数
int i;
for(i=1; i<=r; i++) //根据规模范围输出
printf("%2d",ans[i]);//保留位常宽
cout<<endl;
}
void dfs(int k) { //深搜函数，当前是第k格
int i;
if(k==r){ //填满了的时候
print();//输出当前解
return;
}
for(i=1; i<=n; i++) { //1-n循环填数
if(pd[i]==0) { //如果当前数没有用过
pd[i]=1;//标记一下,1表示当前这个数字使用过
ans[k+1]=i;//把这个数填入结果数组
dfs(k+1);//填下一个
pd[i]=0;//回溯
}
}
}
int main() {
cin>>n>>r;//读入规模和要选几个数
dfs(0);//注意，这里是从第0格开始的！
return 0;
}
当我们输入 3 2 时，输出结果是
1 2
1 3
2 1
2 3
3 1
3 2很明显，不符合题意，因为在原题中，2 1 和1 2 是同一种选法。
实际上，下面这都是同一种选法。
所以，对于搜索和回溯算法这种来说，还有一个问题就是不允许重复项。
所以，上面这个程序的问题在什么地方?
我们举例来说， 从3个中选两个，第一次选了 1 2，根据代码结构我们会回溯回去选1 3。但是当我们第二轮开始选数的时候却不能选2 1。
可以看出一个什么规律呢？
1 2
1 3
2 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同样是这样，那么我们就要控制条件制造出这样的数据。我们每次for循环的时候只要从上一步的值开始遍历就行了，这样就永远不会取到比原来小的数了。
【参考代码2】
#include<bits/stdc++.h>
using namespace std;
int n,r; //定义一共几个数，需要选几个数
int pd[100],ans[100];//pd数组是判断是否用过这个数，ans是结果数组
void print() { //输出函数
int i;
for(i=1; i<=r; i++) //根据规模范围输出
printf("%d ",ans[i]);//保留位常宽
cout<<endl;
}
void dfs(int k) { //深搜函数，当前是第k格
int i;
if(k==r){ //填满了的时候
print();//输出当前解
return;
}
for(i=ans[k]; i<=n; i++) { //1-n循环填数,先从上一步的数据开始，
if(pd[i]==0) { //如果当前数没有用过
pd[i]=1;//标记一下,1表示当前这个数字使用过
ans[k+1]=i;//把这个数填入结果数组
dfs(k+1);//填下一个
pd[i]=0;//回溯
}
}
}
int main() {
cin>>n>>r;//读入规模和要选几个数
ans[0]=1;// 因为要用到上一步的值，所以开始的时候要给初值，不然就会取到0
dfs(0);//注意，这里是从第0格开始的！
return 0;
}
返回目录：题解目录