本文共 1335 字，大约阅读时间需要 4 分钟。

题目来自：

题目描述

已知 n个整数 x1,x2,…,xn，以及1个整数k(k<nk<n)。从n个整数中任选kk个整数相加，可分别得到一系列的和。例如当n=4,k=3n=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。

输入输出格式

键盘输入，格式为：

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

x1 ,x 2 ,…,x n(1≤x i≤5000000) 输出格式： 屏幕输出，格式为： 11个整数（满足条件的种数）。

输入输出样例

输入样例#1： 4 3 3 7 12 19 输出样例#1： 1

---

思路：

这是一道典型的递归问题，要注意的是 ：这里质数判断有多种方法，我选择的是使用质数表，0为质数，1为非质数（0,1不是质数，2是最小的质数）。

然后递归，递归函数输入参数num1代表还需要选择的数字个数，sum代表已选择数字的和，flag代表未选择的数字从数组的下标为flag开始找。 边界条件：如果未选择的数字为0，并且和不是质数就返回0，反之返回1.还可以使用一个剪枝缩小范围：未选择的数字+开始位置>数组长度就没必要继续递归了，直接返回0

---

直接撸代码了：

import java.util.*;public class Main {    private static int num;    private static int[] a = new int[22];    private static int[] number = new int[15000010];//质数表    public static void init(){        for(int i=2;i<15000010;i++){            if(number[i]==0){//0为质数                for(int j=i+i;j<15000010;j+=i){                    number[j]=1;                }            }        }        return;    }    public static int rec(int num1,int sum,int flag){//num表示还有几个位置没排好，sum是排好数的和，flag是接下来没排好的数从哪个下标开始。        if(num1==0){            if(number[sum]==0){                return 1;            } else{                return 0;            }        }        if(flag+1-1+num1>num){            return 0;        }        int total = 0;        for(int i=flag;i