题目描述

排列与组合是常用的数学方法，桐桐刚刚学会了全排列，就想试试组合，组合就是从 n 个元素中抽出 r 个元素（不分顺序且 r ≤ n），我们可以简单地将 n 个元素理解为自然数 1，2，...，n，从中任取 r 个数。

输入格式

两个整数 n 和 r（1 ≤ r ≤ n ≤ 20）。

输出格式

输出所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，所有的组合也按字典顺序。

样例

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

解题思路

这条题和前面学的 DFS 例题很类似的，大方向还是按照之前的思路，也就是说，我们给 x[i] 数组填数，填够 r 个了，就输出。差别在于填数字的时候的规则是灵活多边的，要结合题目的描述。

题目说的，每一种组合都按照从小到大的顺序排列，也就是说 {3,4,5} 这个组合是不能按照 {4,3,5} 来输出的。既然这样，我们就应该充分利用这个条件，我们填 x[l] 的时候，要设置一个条件 x[l] > x[l-1]。这个条件，是我们分析出来的，题目没有很明确的说。我们用上这个条件之后， dfs 的过程就会少走冤枉路。我们不希望枚举一堆不合理的方案，然后再来检验剔除，我们更希望在枚举的时候只枚举那些有意义的值，尽可能少的检验，甚至不需要检验，这才会使得你的程序运行得高效，才不容易超时.

完善程序

#include<bits/stdc++.h>
using namespace std;
int x[21],n,r;
void dfs(int l)
{
	int i;
	if(l==填空(1))
	{
		for(i=1;填空(2);i++)
			printf("%d ",x[i]);
		
		printf("\n");
	}
	else
	{
		for(i=填空(3);i<=n;i++)
		{
			x[l] = i;
			填空(4) ;
		}
	}
}

int main()
{	
	scanf("%d %d",&n,&r); 

	填空(5);	

	return 0;
}

填空(1):{{ input(1) }}

填空(2):{{ input(2) }}

填空(3):{{ input(3) }}

填空(4):{{ input(4) }}

填空(5):{{ input(5) }}