7-3 前t个组合结果 (25 分)

7-3 前t个组合结果 (25 分) 题目

找出从自然数1、2、… 、n（0 输入格式

在一行中输入n、r、t（1<=t<=C(n,r））。

输出格式

按特定顺序输出前t个组合结果，每一个组合结果占一行，含第一个整数在内的每一个整数前面都用一个空格，最后一个整数后面没有空格。 特定顺序：每一个组合结果中的值从大到小排列，组合之间按逆字典序排列。

输入样例

5 3 10

6 4 8

输出样例

 5 4 3
 5 4 2
 5 4 1
 5 3 2
 5 3 1
 5 2 1
 4 3 2
 4 3 1
 4 2 1
 3 2 1

 6 5 4 3
 6 5 4 2
 6 5 4 1
 6 5 3 2
 6 5 3 1
 6 5 2 1
 6 4 3 2
 6 4 3 1

基本思路

有点类似于全排列问题的变式，用回溯的思想解决。

代码

#include 
using namespace std;

int n,r,t;//1~n；取几个数字；共需要几组组合
int m=0;//满足条件的组合个数
int a[35],book[35];//存放一组组合；下标为某个数字，值表示这个数字能否被取走
//pos代表这次dfs需要填充数组a的哪个位置，n代表这次dfs中i从n开始逆向枚举到1（还需要经过数组book判断这个i到底能不能取走）
void dfs(int n,int pos){
    //程序终止
    if(m==t){//组合个数已经够了，直接退出程序，减少运行时间
        exit(0);
    }
    //递归边界，返回最近一次调用dfs函数的地方
    if(pos>r){//在一组组合中，只取r个数字，在取第r+1个数字的dfs中，回溯
        return;
    }
    for(int i=n;i>=1;i--){//枚举i从n到1
        if(book[i]==0){
            book[i]=1;
            a[pos]=i;
            //如果当前数组下标等于要取的数字个数，说明一组组合已经生成，输出                                                                                                           
            if(pos==r){
                m++;//组合数加1
                for(int j=1;j<=pos;j++){
                    cout<<" "<>n>>r>>t){
        dfs(n,1);//从(int n=n,int pos=1)开始dfs
    } 
}