回溯法求组合数-题解（C语言代码）

解题思路:

       利用回溯法来求解组合数，我们可以把组合数当成为n个小球抽取m个小球的办法，利用二叉树，n个小球就有n层，用数组x[k]为1时装入左子树，为0时装入右子树，别界条件为没有到达叶结点时，到达m时就回到上一层，进行另一子树，到达叶子点时，如果等于m时就记录下来。以c(4,2)为例：

注意事项:注意累加的初始变化，num和bestnum的在程序变化，while(~scanf("%d%d",&n,&m))这个功能是循环从输入流读取m和n 直到遇到EOF为止等同于while (scanf("%d%d",&m,&n)!=EOF)。

参考代码:

#include

#define N 30

int x[N];

int a[N][N];

int num=0;

int bestnum=0;

void backtrack(int k,int n,int m)

{

int i;

if(k>n)

{

if(num==m){

bestnum++;

}

}

else{

    for(i=0;i<=1;i++)

{

  x[k]=i;

  if(i==0)

backtrack(k+1,n,m);

  else

  {

 if(num<=m)

 {

      num=num+1;

  backtrack(k+1,n,m);

  num=num-1;

}

}

}

}

}

void main()

{

int n,m;

while(~scanf("%d%d",&n,&m))

{

   backtrack(1,n,m);

       printf("%ld\n",bestnum);

   num=0;

   bestnum=0;

}

}