# C语言程序设计100例之（32）：组合问题

#### 例32  组合问题

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

##### （1）编程思路。

用递归来完成。

设函数void dfs(int pos,int num)表示为第pos（0≤pos≤r-1）个数取值，取值可以为num~n之一。显然，若r-pos>n-num+1，则后面剩下的数不够，直接剪枝；否则，在num~n中取一个数i（num≤i≤n）赋给a[pos]，继续为下一个位置pos+1取数，即递归调用函数dfs（pos+1,i+1）。

##### （2）源程序。

#include <stdio.h>

int a[21],n,r;

void dfs(int pos,int num)

{

if (pos==r)   // 已有r个数

{

for (int i=0;i<r;i++)

printf("%3d",a[i]);

printf(" ");

return;

}

if(r-pos>n-num+1) return ;

for(int i=num;i<=n;i++)

{

a[pos]=i;

dfs(pos+1,i+1);

}

}

int main()

{

scanf("%d%d",&n,&r);

dfs(0,1);

return 0;

}

#### 习题32

##### 32-1  Lotto

本题选自北大OJ题库 （http://poj.org/problem?id=2245）

Description

In the German Lotto you have to select 6 numbers from the set {1,2,...,49}. A popular strategy to play Lotto - although it doesn"t increase your chance of winning - is to select a subset S containing k (k > 6) of these 49 numbers, and then play several games with choosing numbers only from S. For example, for k=8 and S = {1,2,3,5,8,13,21,34} there are 28 possible games: [1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ... [3,5,8,13,21,34].

Your job is to write a program that reads in the number k and the set S and then prints all possible games choosing numbers only from S.

Input

The input will contain one or more test cases. Each test case consists of one line containing several integers separated from each other by spaces. The first integer on the line will be the number k (6 < k < 13). Then k integers, specifying the set S, will follow in ascending order. Input will be terminated by a value of zero (0) for k.

Output

For each test case, print all possible games, each game on one line. The numbers of each game have to be sorted in ascending order and separated from each other by exactly one space. The games themselves have to be sorted lexicographically, that means sorted by the lowest number first, then by the second lowest and so on, as demonstrated in the sample output below. The test cases have to be separated from each other by exactly one blank line. Do not put a blank line after the last test case.

Sample Input

7 1 2 3 4 5 6 7

8 1 2 3 5 8 13 21 34

0

Sample Output

1 2 3 4 5 6

1 2 3 4 5 7

1 2 3 4 6 7

1 2 3 5 6 7

1 2 4 5 6 7

1 3 4 5 6 7

2 3 4 5 6 7

1 2 3 5 8 13

1 2 3 5 8 21

1 2 3 5 8 34

1 2 3 5 13 21

1 2 3 5 13 34

1 2 3 5 21 34

1 2 3 8 13 21

1 2 3 8 13 34

1 2 3 8 21 34

1 2 3 13 21 34

1 2 5 8 13 21

1 2 5 8 13 34

1 2 5 8 21 34

1 2 5 13 21 34

1 2 8 13 21 34

1 3 5 8 13 21

1 3 5 8 13 34

1 3 5 8 21 34

1 3 5 13 21 34

1 3 8 13 21 34

1 5 8 13 21 34

2 3 5 8 13 21

2 3 5 8 13 34

2 3 5 8 21 34

2 3 5 13 21 34

2 3 8 13 21 34

2 5 8 13 21 34

3 5 8 13 21 34

（1）编程思路。

本题的意思是要在有k个元素的集合S中任意取6个元素，并输出所有这些取值组合。

设 combine(int take[], int len, int count,int num[])为从具有len个元素的数组num中取出count个元素，并将取出的元素存放在数组a中。

为求解combine(int take[], int len, int count,int num[])，可以先在len个元素的数组num的后面取第一个元素num[i]放在a[count-1]中，所取的第一个数组元素的下标i可以是len-1,len-2,…,count-1。注意：第一个取的数组元素的下标i不能取count-2，因为后面的要取的元素均会在第一个取的元素的前面，因此最多只能取出0~count-3共count-2个不同的y元素，达不到取count个数的目的。

在将确定组合的第一个元素num[i]放入数组take后，有两种选择：还未确定组合的其余元素时（count>1，即还需取count-1个元素），继续递归comb(take,i,count-1,num)确定组合的其余元素，即在num[0]~num[i-1]这i个元素中取count-1个数；已确定组合的全部元素时（count==1），输出这个组合。

（2）源程序。

#include <stdio.h>

void combine(int take[], int len, int count,int num[])

{

int i,j;

for (i = len-1; i >= count-1; i--)

{

take[count - 1] = num[i];

if (count >1)

combine(take, i , count - 1, num);

else

{

for (j = 6-1; j >=0; j--)

{

printf("%d ",take[j]);

}

printf(" ");

}

}

}

int main()

{

int i,k,num[13],take[6],t;

while(scanf("%d",&k) && k!= 0)

{

for(i = 0; i < k; i++)

scanf("%d",&num[i]);

for (i=0;i<k/2;i++)

{

t=num[i];

num[i]=num[k-i-1];

num[k-i-1]=t;

}

combine(take,k,6,num);

printf(" ");

}

return 0;

##### 32-2  选数

本题选自洛谷题库 （https://www.luogu.org/problem/P1036）

3+7+12=22

3+7+19=29

7+12+19=38

3+12+19=34。

n,kn,k(1≤n≤20,k<n)

x1 ,x2 ,…,xn (1≤xi ≤5000000)

1个整数（满足条件的种数）。

4 3

3 7 12 19

1

（1）编程思路。

编写递归函数void dfs(int pos,int num)完成n个数中取k个数。然后判断每种取值组合的和是否为一个素数。

（2）源程序。

#include <stdio.h>

#include <math.h>

int a[21],b[22],n,k,cnt=0;

int isPrime(int num)

{

if (num==1) return 0;

for (int m=2;m<=(int)sqrt((double)num);m++)

if (num%m==0) return 0;

return 1;

}

void dfs(int pos,int num)

{

if (pos==k)   // 已有k个数

{

int sum=0;

for (int i=0;i<k;i++)

sum+=a[i];

if (isPrime(sum)) cnt++;

return;

}

if(k-pos>n-num+1) return ;

for(int i=num;i<=n;i++)

{

a[pos]=b[i];

dfs(pos+1,i+1);

}

}

int main()

{

scanf("%d%d",&n,&k);

for (int i=1;i<=n;i++)

scanf("%d",&b[i]);

dfs(0,1);

printf("%d ",cnt);

return 0;

}

##### 32-3  加法变乘法

1+2+3+...+10*11+12+...+27*28+29+...+49 = 2015

2015

10 27

16 24

（1）编程思路。

问题实际上是在1~48这个48个数字中任选两个数字。选择了这两个数字后，判断将两个数字后面的加号变成乘号后，表达式的值是否等于给定的N。

（2）源程序。

#include <stdio.h>

int a[3],n,found=0;

void dfs(int pos,int num)

{

if (pos==2)

{

int t=1225-2*(a[0]+a[1]+1)+a[0]*(a[0]+1)+a[1]*(a[1]+1);

if (a[1]-a[0]!=1 && t==n)

{

printf("%d %d ",a[0],a[1]);

found=1;

}

return;

}

if(2-pos>48-num+1) return ;

for(int i=num;i<=48;i++)

{

a[pos]=i;

dfs(pos+1,i+1);

}

}

int main()

{

scanf("%d",&n);

dfs(0,1);

if (found==0) printf("No solution! ");

return 0;

}