题目描述
已知 nn 个整数 x_1,x_2,\cdots,x_nx1​,x2​,⋯,xn​，以及 11 个整数 kk（k<nk<n）。从 nn 个整数中任选 kk 个整数相加，可分别得到一系列的和。例如当 n=4n=4，k=3k=3，44 个整数分别为 3,7,12,193,7,12,19 时，可得全部的组合与它们的和为：

3+7+12=22

3+7+19=29

7+12+19=38

3+12+19=34

现在，要求你计算出和为素数共有多少种。

例如上例，只有一种的和为素数：3+7+19=29。

输入格式
第一行两个空格隔开的整数 n,kn,k（1 \le n \le 201≤n≤20，k<nk<n）。

第二行 nn 个整数，分别为 x_1,x_2,\cdots,x_nx1​,x2​,⋯,xn​（1 \le x_i \le 5\times 10^61≤xi​≤5×106）。

输出格式
输出一个整数，表示种类数。

输入输出样例
输入 #1复制

4 3
3 7 12 19
输出 #1复制

1
说明/提示
【题目来源】

NOIP 2002 普及组第二题

解题思路：

这题我看网上主要是就是通过dfs，比如输入

4 3
3 7 12 19

在dfs哪里，m代表现在加了几次，sum代表加的和，statrt，代表他下一个要加的索引位置，比如第一组数组就是：

1 3 2

1 7 3

1 12 4

1 19 5

会进行这4次递归，我通过第一组递归讲1 3 2，那么他第二次就是2 10 3，其中的10—>3+7,为什么要加7，因为1 3 2最后一个要代表他加的位置，那就是2，进行这次递归后就是2 10 3—>3 22 4，此时m是3，然后代表已经加3次了，可以进行素数判断了，跳出递归,这只是1 3 2里的其中一组数据，还有一组就是2 10 3->3 29 4，此时m=3，可以进行素数判断了

废话不多说，上代码

import java.util.Scanner;

public class Main {
    static int ans = 0;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int[] arr = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            arr[i] = in.nextInt();
        }

        dfs(0, 0, 1, arr, k);
        System.out.println(ans);
    }

    public static void dfs(int m, int sum, int start, int[] arr, int k) {
        if (m == k) {
            if (isPrime(sum)) {
                ans++;
            }
            return;
        }
        for (int i = start; i < arr.length; i++) {
            dfs(m + 1, sum + arr[i], i + 1, arr, k);
        }
    }
    public static boolean isPrime(int num)//判断质数
    {
        for (int i = 2 ; i <= Math.sqrt(num) ; i++)
        {
            if (num % i == 0)
            {
                return false;
            }
        }
        return true;
    }
}