组合数打印
//[北京直真笔试题]比如给定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）。
const int g_nCnt = 4;
int g_nArr[g_nCnt] ={1,2,3,4};
//从3个里面选2个数的排列方式.
void selTwoFromThree(intnArray[], int nSize, int nAlreadySel)
{
for(int i = 0; i < nSize; i++)
{
for(int j = i+1; j < nSize; j++)
{
cout << nAlreadySel << "\t"<< nArray[i] << "\t" << nArray[j] << endl; //先i后j
cout << nAlreadySel << "\t"<< nArray[j] << "\t" << nArray[i] << endl; //先j后i
}
}
}
void printArray(intnArray[], int nSize)
{
int nAleardySel = 0;
for(int i = 0; i < nSize; i++)
{
int *pArrAdd = new int[3];
int k = 0;
nAleardySel = nArray[i];
for(int j = 0; j < nSize; j++)
{
if(nArray[j] != nAleardySel)
{
pArrAdd[k++] = nArray[j];
}//end if
}//end for j
selTwoFromThree(pArrAdd,g_nCnt-1,nAleardySel);
cout << endl;
}//end fori
}
方法2：【思路】 将4个数中选择的3个数看做百位数，因此就变成了打印的过程，变成了从4个数中选3个数组成的全排列4*4*4=64个中选择百位、十位、个位不重复的4*3*2=24个数的过程。
【分析】：时间复杂度O（n3），空间复杂度O（1）。不需要额外的开辟空间。
#define MAXN 4
void combineSelPrint(intmaxCnt)
{
static int count = 0;
for(int i=1;i<=MAXN;i++)//百位的情况
{
for(int j=1;j<=MAXN;j++)//十位的情况
{
if(j != i)
{
for(int k=1;k<=MAXN;k++)//个位的情况
{
if(k != j && k != i)
{
printf("%d,%d,%d\n",i,j,k);
++count;
}
}//end for k
}//end if j
}//end for j
}//end for i
cout << "--------------count = " << count<< "-------------" << endl;
}
int main()
{
combineSelPrint(MAXN);
return 0;
}
【思考？】：有没有时间复杂度低的算法？或者递归实现的好方法？
【方法3】：递归实现组合数打印，C（n，m），从n个数中选出m个数（m<=n）个的全部组合打印。
有很多文章讨论如何打印全排列的，毕竟它是很多遍历问题的基础嘛。这里介绍的是如何打印组合数。
先看一个例子：
C(5,3) = 10
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
大家注意到没有，
1 | 2 3
1 | 2 4
1 | 2 5
1 | 3 4
1 | 3 5
1 | 4 5
------ C(4, 2)∵可以在{2, 3, 4, 5}中挑2个出来。
2 | 3 4
2 | 3 5
2 | 4 5
------ C(3, 2)∵可以在{3, 4, 5}中挑2个出来。
3 | 4 5
------ C(2, 2)∵只能在{4, 5}中挑2个出来。
这样就很容易写出递归算法来。
Algorithm combination（n, k, A[l..n+l-1]）
1. if k = 0
2. print ary[1..k]
3. else
4. for i←1 to n-k+1
5. ary[index++] = A[l+i-1]
6. combination（n-i,k-1, A[l+i..n+l-1]）
7. --index
8. endfor
大家可能会疑惑干嘛要弄出个index，还有一加一减的（你手工算一下就知道了）。
【实现部分】
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
笔者调试了方法三，好用。但是笔者对其中递归的部分的原理甚是不解，有些疑惑，望大家介绍下。
