递归（四）：组合
排列组合是组合学最基本的概念。所谓排列，就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。
排列与组合在日常生活中应用较广，比如在考虑某些事物在某种情况下出现的次数时，往往需要用到排列和组合。
【例1】取值组合。
有一个集合拥有m个元素{1，2，…，m}，任意的从集合中取出n个元素，则这n个元素所形成的可能子集有哪些？
假设有5个元素的集合，取出3个元素的可能子集如下：
{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}。
编写一个程序，输入整数m和n，输出m个元素中，取出n个元素的各种情况。
（1）编程思路。
用递归程序来解决问题。
从m个数中，取出n个数的所有组合。设m个数已存于数组a[1..m]中。为使结果唯一，可以分别求出包括a[m]和不包括a[m]的所有组合。即包括a[m]时，求出从a[1..m-1]中取出n-1个元素的所有组合（子问题，递归）；不包括a[m]时，求出从a[1..m-1]中取出n个元素的所有组合（同样是子问题，递归）。
（2）源程序。
#include <iostream>
using namespace std;
#define maxsize 20
void nkcombination(int i,int k,int j,int a[],int b[])
// 从n（a[0]）个数中连续取出k个数的所有组合，n个数已存入数组a中。
// i为待取数在数组a中的下标，j为结果数组b中的下标。
{
if (k==0)
{
for (int p=1;p<=b[0];p++)
cout<<b[p]<<" ";
cout<<endl;
}
else if (i+k-1<=a[0])
{
b[j]=a[i]; j++;
nkcombination(i+1,k-1,j,a,b);
// 包括a[i]时，递归求出从a[i+1..n]中取出k-1个元素的所有组合
nkcombination(i+1,k,j-1,a,b);
// 不包括a[i]时，递归求出从a[i+1..n]中取出k个元素的所有组合
}
}
int main()
{
int set[maxsize],result[maxsize];
int m,n,i;
cout<<"输入给定元素个数 m ：";
cin>>m;
for (i=1;i<=m;i++)
set[i]=i;
cout<<"输入取出元素个数 n：";
cin>>n;
set[0]=m; result[0]=n;
nkcombination(1,n,1,set,result);
return 0;
}
【例2】选数。
已知n个整数x1，x2，…，xn，以及一个整数k（k＜n）。从n个整数中任选k个整数相加，可分别得到一系列的和。例如当n=4，k＝3，4个整数分别为3，7，12，19时，可得全部的组合与它们的和为：3＋7＋12=22，3＋7＋19＝29，7＋12＋19＝38，3＋12＋19＝34。编写一个程序计算出和为质数的组合共有多少种。
例如上例，只有一种组合的和为质数：3＋7＋19＝29。
（1）编程思路。
本例是求从n个数中选k个数的组合，并使其和为素数。求解此题时，先按例1的方法生成k个数的组合，再判断k个数的和是否为质数，若为质数则输出和式并计数。
（2）源程序。
#include <iostream>
#include <cmath>
using namespace std;
#define maxsize 20
int cnt=0;
bool isprime(int num)
{
int m;
if(num==2) return true;
for(m=2;m<=(int)sqrt((double)num);m++)
if (num%m==0)
return false;
return true;
}
void nkcombination(int i,int k,int j,int a[],int b[])
{
if (k==0)
{
int p,s;
for (p=1,s=0;p<=b[0];p++)
s=s+b[p];
if (isprime(s))
{
cnt++;
for (p=1;p<b[0];p++)
cout<<b[p]<<" + ";
cout<<b[p]<<"="<<s<<endl;
}
}
else if (i+k-1<=a[0])
{
b[j]=a[i]; j++;
nkcombination(i+1,k-1,j,a,b);
nkcombination(i+1,k,j-1,a,b);
}
}
int main()
{
int set[maxsize],result[maxsize];
int n,k,i;
cout<<"输入给定整数的个数 n ：";
cin>>n;
cout<<"依次输入"<<n<<"个整数：";
for (i=1;i<=n;i++)
cin>>set[i];
cout<<"输入取出元素个数 k：";
cin>>k;
set[0]=n; result[0]=k;
nkcombination(1,k,1,set,result);
cout<<"count="<<cnt<<endl;
return 0;
}