Life has its own fate, and meeting may not be accidental.

0%

pta-7-49 前t个组合结果 (25分)DFS

题目

组合结果
找出从自然数1、2、… 、n(0<n<=30)中任取r(0<r<=n)个数的组合,输出其中前t个组合结果。

输入格式:

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

输出格式:

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

输入样例:

1
5 3 10
1
6 4 8

输出样例:

1
5 4 3
2
5 4 2
3
5 4 1
4
5 3 2
5
5 3 1
6
5 2 1
7
4 3 2
8
4 3 1
9
4 2 1
10
3 2 1
1
6 5 4 3
2
6 5 4 2
3
6 5 4 1
4
6 5 3 2
5
6 5 3 1
6
6 5 2 1
7
6 4 3 2
8
6 4 3 1

代码:

1
#include<bits/stdc++.h>
2
using namespace std;
3
int n,m,r,t,sum;
4
int f[100]={0}; 
5
int vis[100];
6
void dfs(int x,int cnt){
7
	if(sum==t){     //如果到数了退出
8
		return;
9
	}
10
	if(cnt-1==m){
11
		sum++;
12
		for (int i=1;i<=m;i++){
13
			printf(" %d", f[i]);
14
		}
15
		printf("\n");
16
	}
17
	else{
18
		for(int i=x;i>0;i--){
19
			if(!vis[i]){
20
				vis[i]=1;//标记
21
				f[cnt]=i;//计数
22
				dfs(i-1,cnt+1);
23
				vis[i]=0;
24
			}
25
		}
26
	}
27
}
28
int main(){
29
	scanf("%d %d %d",&n,&m,&t);
30
	memset(vis,0,sizeof(vis));
31
	sum=0;
32
	dfs(n,1);
33
	return 0;
34
}