【题目描述】

排列与组合是常用的数学方法,其中组合就是从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;
}

返回目录:题解目录