/*===================================== 数的组合问题。从1,2,…,n中取出m个数，将所有组合按照字典顺序列出。 如n=3,m=2时，输出： 1 2 1 3 2 3 这里只考虑从互不相同的n个数当中选择m个的情况。 我的思路：
这里采用的思路和上回解决递归生成全排列的思路差不多。
从a数组的n个数当中选m个到ans数组。
每一次选择一个数到ans[i]时都在a数组中扫描并依次选择所有的可能。
但是这里扫描的范围是从ans[i-1]在a中的下标k的下一个开始，一直扫描到n-（m-i-1）的前一个位置为止。
这个范围是ans[i]的可能选择的范围。（后面还要选一部分才凑够m个数，故不能扫描到a数组的末尾。）
======================================*/
1 #include<stdio.h> 2 int count=0; 3 void fun(int a[],int n,int m,int i,int k,int ans[]); 4 //原始数组a[],从a数组的n个数当中选m个数，结果放在ans数组。 5 //i表示当前要选取第i个数。i从0开始。k表示上一次选取的数在a数组当中的下标。 6 //最开始时k==-1,表示还没选数据。 7 int main() 8 { 9 int n,m,a[30],ans[30],i; 10 freopen("5.out","w",stdout); 11 scanf("%d%d",&n,&m); 12 for(i=0;i<n;i++) 13 { 14 //scanf("%d",&a[i]); 15 a[i]=i+1; 16 } 17 fun(a,n,m,0,-1,ans); 18 printf("%d\n",count); 19 return 0; 20 } 21 void fun(int a[],int n,int m,int i,int k,int ans[]) 22 //原始数组a[],从a数组的n个数当中选m个数，结果放在ans数组。 23 //i表示当前要选取第i个数。i从0开始计数。k表示上一次选取的数在a数组当中的下标。 24 //最开始时k==-1,表示还没选数据。 25 { 26 int j; 27 if(i==m) 28 { 29 for(j=0;j<m;j++) printf("%d ",ans[j]); 30 printf("\n"); 31 count++; 32 return ; 33 } 34 else 35 { 36 for(j=k+1;j<n-(m-i-1);j++)//从第k+1个开始，尝试选择第i个数。(注意：i从0开始计算) 37 { 38 ans[i]=a[j]; 39 fun(a,n,m,i+1,j,ans); 40 } 41 } 42 }
下面是网上的做法，思路挺好的。
来源：http://blog.csdn.net/challenge_c_plusplus/article/details/6641950
原文如下：
此法借鉴了2009年华为一笔试题我写的一个递归算法
http://blog.csdn.net/challenge_c_plusplus/article/details/6640530
排列数的递归实现见我的另一篇
http://blog.csdn.net/challenge_c_plusplus/article/details/6574788
1 /* 2 * 功能：输出组合数C（n，m） 3 * 日期：2011/7/28 4 * 作者：milo 5 * 不足：对于有多个重复数字，会输出重复的组合数，可以通过遍历一个数组链表解决。 6 */ 7 8 #include<stdio.h> 9 #include<stdlib.h> 10 11 int *dst_array,top=0,count=0;//中间数组，存放中间求解过程，count计数所有的组合个数 12 13 //打印长度为n的数组元素 14 static void printA(int *parray,int n) 15 { 16 int i; 17 for(i=0;i<n;i++){ 18 printf("%d ",parray[i]); 19 } 20 } 21 22 //递归打印组合数 23 static void print_combine(int *pArray,int n,int m) 24 { 25 if(n < m || m==0) return ;//情况一：不符合条件，返回 26 print_combine(pArray+1,n-1,m);//情况二：不包含当前元素的所有的组合 27 dst_array[top++]=pArray[0];//情况三：包含当前元素 28 if(m==1){//情况三-1：截止到当前元素 29 printA(dst_array,top); 30 printf("\n"); 31 count++; 32 top--; 33 return; 34 } 35 print_combine(pArray+1,n-1,m-1);//情况三-2：包含当前元素但尚未截止 36 top--;//返回前恢复top值 37 } 38 39 int main() 40 { 41 int n,m,*parray;//存放数据的数组，及n和m 42 scanf("%d%d",&n,&m); 43 parray=(int *)malloc(sizeof(int)*n); 44 dst_array=(int *)malloc(sizeof(int)*m); 45 int i; 46 for(i=0;i<n;i++){//初始化数组 47 scanf("%d",&parray[i]); 48 } 49 print_combine(parray,n,m);//求数组中所有数的组合 50 printf("=====C（%d，%d）共计：%d个=====",n,m,count); 51 return 0; 52 }
