202013 - 组合问题

题解byzzq_helloworld

题目很简单

一般地，从n个不同的元素中，任取m（m≤n）个元素为一组，叫作从n个不同元素中取出m个元素的一个组合，我们把有关求组合的个数的问题叫作组合问题。 现有n个数，分别为1，2，3，…，n－1，n，从中选出m个数，试输出所有组合方案。

递归题只要找到递归的东西，就可以解出来了，我们首先来看一下具体的思路：

这一题我们可以用深搜。首先，我们先定义一个数组，用来存放是否被用，然后从下一个数据出发不停深搜，如果已经到满足条件，则输出。

源代码如下：

#include<bits/stdc++.h>
using namespace std;

int n,m,a[30];//n是不同元素的个数,m是目标的数值个数，a是数值数组

void DFS(int k)//k为目前选了多少个数
{
  if(m==k)//如果已经选择了足够的数，则输出
  {
    for(int i=0; i<k; i++)
      cout<<a[i];
    cout<<endl;
  }
  else
  {
    //上一个值往后加1，如现在为12，则第三个值至少为3
	a[k]=a[k-1]+1;
    for(; a[k]<=n; a[k]++)//从a[k-1]加1开始枚举递归出下一个值
      DFS(k+1);//递归
  }
}

int main()
{
  cin>>n>>m;
  DFS(0);//递归
  return 0;
}

最后说一句，不要抄题解！