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;
}

最后说一句,不要抄题解!