题目描述
已知 n 个整数b1,b2,…,bn
以及一个整数 k（k＜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。
现在，要求你计算出和为素数共有多少种。
例如上例，只有一种的和为素数：3＋7＋19＝29。
输入
第一行两个整数：n , k （1<=n<=20，k＜n）
第二行n个整数：x1,x2，…,xn （1<=xi<=5000000）
输出
一个整数（满足条件的方案数）。
样例输入
4 3 3 7 12 19
样例输出
1
常规的dfs遍历题，但有一点想了好久才想到，需要注意的是：选中数字后，如 3， 7， 19。即3+7+19只能算是一种和为素数的方案 。之前一直不能理解这一点，害的我样例输出一直是6！！！
C++代码如下:
#include<iostream>
#include<cmath>
#include<algorithm>
#include<map>
using namespace std;
const int maxn = 25;
bool vis[maxn] = {false};
int n, k, sum, cnt, arr[maxn];//检查数字num是否素数
bool check(int num){if(num == 1)return false;for(int i = 2; i <= (int)sqrt(1.0 * num); i++)if(num % i == 0)return false;return true;
}
//step:目前在第step个位置尝试放入数字; pre:从第pre个数字开始放入(前面的数字不管，使选中的k个数字是由小到大排序)
void dfs(int step, int pre){if(step == k + 1){if(check(sum))cnt++;return;}for(int i = pre; i <= n; i++){if(!vis[i]){//选中第i个数作为第step个位置 vis[i] = true;sum += arr[i];dfs(step + 1, i+1);//回溯vis[i] = false;sum -= arr[i]; }}return;
}int main(){scanf("%d%d", &n, &k);for(int i = 1; i <= n; i++)scanf("%d", &arr[i]);sum = 0; //和 cnt = 0; //和为素数的方案次数 dfs(1, 1);printf("%d\n", cnt);return 0;
}