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

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

例题：

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

(adsbygoogle = window.adsbygoogle || []).push({});