【题目来源】
洛谷：P1036 [NOIP 2002 普及组] 选数 - 洛谷 (luogu.com.cn)
【题目描述】
已知 \(n\) 个整数 \(x_1,x_2,\dots,x_n\)，以及 \(1\) 个整数 \(k(k\lt 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\le n\le 20, k\lt n)\)。
第二行 \(n\) 个整数，分别为 \(x_1,x_2,\dots, x_n(1\le x_i\le 5\times 10^6)\)。
【输出】
输出一个整数，表示种类数。
【输入样例】
4 3
3 7 12 19
【输出样例】
1
【解题思路】
【算法标签】
《洛谷 P1036 选数》 #搜索# #深度优先搜索,DFS# #素数判断,质数,筛法# #NOIP普及组# #2002#
【代码详解】
#include <bits/stdc++.h>
using namespace std;// 定义全局变量
int n, k, a[25], ans = 0; // n:数字个数, k:选取数量, a:存储数字, ans:结果计数器// 素数判定函数
bool judge(int num) {if (num < 2) return false; // 小于2的数不是素数for (int i = 2; i <= sqrt(num); i++) { // 只需检查到平方根if (num % i == 0) return false; // 能被整除则不是素数} return true; // 否则是素数
}// 组合枚举函数（递归实现）
void f(int flag, int num, int sum) {// flag:当前起始位置, num:剩余需要选择的数字个数, sum:当前累计和// 终止条件：已选够k个数字if (num == 0) {if (judge(sum)) ans++; // 如果和为素数则计数return;}// 剪枝：剩余数字不足以选够k个if (n - flag + 1 < num) return;// 递归枚举所有可能的组合for (int i = flag; i <= n; i++) {f(i + 1, num - 1, sum + a[i]); // 选择当前数字，递归处理后续}return;
}int main() {// 输入数据cin >> n >> k;for (int i = 1; i <= n; i++) {cin >> a[i]; // 读取数字序列}// 从第一个数字开始枚举所有k个数字的组合f(1, k, 0);// 输出满足条件的组合数量cout << ans;return 0;
}
【运行结果】
4 3
3 7 12 19
1