题目描述：已知 n 个整数 x1,x2,…,xn，以及一个整数 k（k＜n）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。要求计算出和为素数共有多少种。
分析：要用深度搜索来做。首先要有一个判断素数的函数，深搜每次两个分支，即选或者不选此数。当选够k个数则判断和是否是素数。本例搜索树如下，左分支选此数，右分支不选，叶子是最后需要判断的数。原来一颗满二叉树通过剪枝少搜索一些。
代码：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
int a[22], n, k, s;
bool is(int x) //判断素数
{
if (x == 0 || x == 1) return false;
if (x == 2) return true;
for( int i = 2; i * i <= x ; i++)
if (x % i == 0)
return false;
return true;
}
void fun(int i, int x, int st) //深搜，参数分别为：选到第几个数，目前加和，还要加几个数
{
if (st == 0) //k个数选完
{
if ( is(x) ) s ++;
return;
}
if (n - i < st) return; //剪枝，剩下的数已经不够选到k个
fun(i + 1, x + a[i], st - 1); //选此数递归
fun(i + 1, x, st); //不选此数递归
}
int main()
{
int i,j;
while(~scanf("%d %d", &n, &k))
{
s = 0;
for( i = 0; i < n; i++)
scanf("%d", &a[i]);
fun(0,0,k);
printf("%d\n", s);
}
return 0;
}
