递归法求组合数C(m,n)

假设这样一个数组：

1　　2　　3　　4　　5

n=5

若 m=3 也就是要求C(3,5)

首先先选第一个数 1

那么剩下的工作就是在2-5之间选择2个数

如果我们没有选择第一个数 选第二个数2

那么剩下的工作就是在3-5之间选择2个数

这样就很好递归了 只需要记录下当前已经选了几个数 当前选的最后一个数是什么 递归即可

#include<bits/stdc++.h>

using namespace std;

int sum=0; //记录总数

void digui(int *a,int *b,int t,int now,int n,int m)
{
    int i;
    if(t==m)   //t记录已经选择了几个数 若=m，输出结果
    {
        for(i=0;i<m;i++)
        cout<<b[i]<<" ";
        cout<<endl;
        sum++;
        return;
    }
    else
    {
        for(i=now;i<=n-(m-t);i++)  //now代表现在可以从哪个数选起
        {
            b[t]=a[i];
            digui(a,b,t+1,i+1,n,m);
        }
    }
}


int main()
{
    int a[10],b[10],i,n,m;   //a为原数组 b存储结果 
    cin>>n>>m;
    for(i=0;i<n;i++)
    cin>>a[i];
    digui(a,b,0,0,n,m);
    cout<<sum<<endl;
}