描述 已知 n 个整数 x1，x2，……，xn，以及 1 个整数 k（k<nk<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 现在，要求你计算出和为素数共有多少种。 输入描述 第一行两个空格隔开的整数 n,k（1≤n≤20，k<n）。 第二行 n 个整数，分别为 x1，x2，……，xn（1 ≤ xi ≤ 5*10^6） 输出描述 输出一个整数，表示种类数。 c++代码

#include <iostream>
#include <vector>
#include <algorithm>

// 判断一个数是否为素数
bool isPrime(int num) {
    if (num <= 1) {
        return false;
    }
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}

// 计算和为素数的种类数
int countPrimeSum(std::vector<int>& nums, int n, int k, int sum, int index) {
    if (k == 0) {
        return isPrime(sum) ? 1 : 0;
    }
    int count = 0;
    for (int i = index; i < n; i++) {
        count += countPrimeSum(nums, n, k - 1, sum + nums[i], i + 1);
    }
    return count;
}

int main() {
    int n, k;
    std::cin >> n >> k;
    std::vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        std::cin >> nums[i];
    }
    
    int count = countPrimeSum(nums, n, k, 0, 0);
    
    std::cout << count << std::endl;
    
    return 0;
}