题目描述
已知 n 个整数 x1?,x2?,?,xn?，以及 1 个整数 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?≤5×1e6）。
输出格式
输出一个整数，表示种类数。
输入输出样例
输入 #1复制
4 3 3 7 12 19
输出 #1复制
1
说明/提示
【题目来源】
NOIP 2002 普及组第二题
解题方法：DFS.
Code:
#include <iostream>
#include <stdio.h>using namespace std;typedef int Status;const int N = 5000010;int n, k, res;
int a[N], p[N];
bool st[N];Status prime(int x)
{if(x == 0 || x == 1) return false;bool flag = true;for(int i = 2; i * i <= x; i ++ ) if(x % i == 0) flag = false;return flag;
}void dfs(int x, int y, int z)
{if(x == k){if(prime(y)) res ++;return ;}for(int i = z; i <= n; i ++ ){if(!st[i]){st[i] = true;dfs(x + 1, y + a[i], i + 1);st[i] = false;}}
}signed main()
{scanf("%d%d", &n, &k);for(int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);dfs(0, 0, 1);cout << res << endl;
}