前面我们写过 全排列和排列数 等。

这篇文章。我们写一下组合数。

例题：

从n个数中，选出m个，一共有多少种不同的选法？

这是一道典型的组合数公式。我们直接用dfs公式肯定会出现重复的。

#include<bits/stdc++.h>
using namespace std;
int n,m;
int pd[100],ans[100];//pd数组是判断是否用过这个数，ans是结果数组
void print() { //输出函数
   int i;
   for(i=1; i<=m; i++)
       printf("%2d",ans[i]);//保留位常宽
   cout<<endl;
}
void dfs(int k,int f) { //深搜函数，当前是第k格
   int i;
   if(k==m) { //填满了的时候
       print();//输出当前解
       return;
   }
   f++;
   for(i=f; i<=n; i++) { //1-n循环填数
       if(pd[i]==0) { //如果当前数没有用过
           pd[i]=1;//标记一下,1表示当前这个数字使用过
           ans[k+1]=i;//把这个数填入结果数组
                      dfs(k+1,i);//填下一个
           pd[i]=0;//回溯
       }
   }
}
int main() {
   cin>>n>>m;
   dfs(0,0);//注意，这里是从第0格开始的！
   return 0;
}