组合数打印
组合数打印

//[北京直真笔试题]比如给定4个数,分别为1,2,3,4。现在要求从中选取3个的组合数，不能重复。

即打印：123，124，234...。

方法1：【思路】1）将1,2,3,4存入数组中，然后从4个数中选出1个数，即为selVal；2）接下来的工作即是从剩余的3个数中选取2个数，需要存储除selVal外的剩余3个数；3）选取后打印selVal和选的2个数即可。

【分析】：时间复杂度O（n3），空间复杂度O（n）。

int *dst_array,top=0;//中间数组，存放中间求解过程，count计数所有的组合个数int cnt = 0; //打印长度为n的数组元素static void printA(int*parray,int n){    int i;    for(i=0;i<n;i++)    {        printf("%d ",parray[i]);    }} //递归打印组合数static  void print_combine(int *pArray,int n,int m){    if(n < m || m==0)      {           return ;//情况一：不符合条件，返回    }     print_combine(pArray+1,n-1,m);//情况二：不包含当前元素的所有的组合     dst_array[top++]=pArray[0];//情况三：包含当前元素    if(m==1)     {  //情况三-1：截止到当前元素        printA(dst_array,top);        printf("\n");        cnt++;        top--;        return;    }     print_combine(pArray+1,n-1,m-1);//情况三-2：包含当前元素但尚未截止    top--;//返回前恢复top值} int main(){    int n,m,*parray;//存放数据的数组，及n和m    printf("---以下实现从n个数中选出m个数的全组合打印(n个数为1,2,3....n---\n");    printf("---请输入n 和m \n---");    scanf("%d%d",&n,&m);     printf("\n---以下是输出结果---\n");    parray=(int *)malloc(sizeof(int)*n);    dst_array=(int *)malloc(sizeof(int)*m);     int i;    for(i=0;i<n;i++)    {           //初始化数组        //scanf("%d",&parray[i]);           parray[i] = i+1;    }    print_combine(parray,n,m);//求数组中所有数的组合     printf("=====C（%d，%d）共计：%d个=====",n,m,cnt);     free(parray);    free(dst_array);    return 0;}

方法三参考：http://bbs.pfan.cn/post-270256.html

http://blog.csdn.net/challenge_c_plusplus/article/details/6641950

笔者调试了方法三，好用。但是笔者对其中递归的部分的原理甚是不解，有些疑惑，望大家介绍下。