浅浅氵一篇特地写篇笔记
假设手头有 n 个数字，需要从中选出 k 个不同的数字相加。问题是：有多少种选法，能让这 k 个数字的和是质数？
举个简单的例子：
有数字：3, 7, 12, 19
要从中选 3 个数字相加
那么所有可能的组合是：
3+7+12=22（不是质数）
3+7+19=29（是质数！）
3+12+19=34（不是质数）
7+12+19=38（不是质数）
所以答案是：只有 1 种选法能得到质数和。
核心思路分析
这个问题看似简单，但涉及到几个关键点：
1. 组合问题 vs 排列问题
这是最开始容易混淆的地方：
组合：{3,7,12} 和 {7,3,12} 是同一个组合，顺序不重要
排列：{3,7,12} 和 {7,3,12} 是不同的排列，顺序很重要
这个问题显然是组合问题，所以需要避免重复计数。
2. 质数判断
质数是只能被1和自身整除的大于1的自然数。比如：2, 3, 5, 7, 11……
判断一个数是不是质数，最直接的方法就是检查它能不能被2到n-1之间的数整除。但是这样太慢了！有个小技巧：只需要检查到 √n 就可以了。
为什么呢？因为如果一个数 n 有大于√n的因子，那它必然有小于√n的对应因子。
代码实现过程
我先把完整的代码展示一下，然后详细解释：
#include<iostream> using namespace std; int n, k, a[100010], b[100010], cnt = 0; bool judge(int y)//判断质数 { if (y < 2) return 0; for (int i = 2; i * i <= y; i++) { if (y % i == 0)return 0; } return 1; } void dfs(int x) { if (x == k + 1) { int sum=0; for (int i = 1; i <= k; i++) { sum += b[a[i]]; } if (judge(sum)) cnt++; return; } for (int i = a[x - 1] + 1; i <= n; i++) { a[x] = i; dfs(x + 1); } } int main() { cin >> n >> k; for (int i = 1; i <= n;i++) { cin >> b[i]; } dfs(1); cout << cnt; return 0; }代码逐行解析
第一部分：头文件和变量声明
#include<iostream> using namespace std; int n, k, a[100010], b[100010], cnt = 0;#include<iostream>：引入输入输出流库，相当于拿到控制台的"遥控器"using namespace std;：打开标准命名空间，这样写cout时就不用写成std::cout了变量声明：
n：总共有多少个数字k：要选几个数字a[100010]：记录选择了哪些数字的位置（索引）b[100010]：存储实际的数字cnt：计数器，记录符合条件的方案数，初始化为0
第二部分：质数判断函数
bool judge(int y)//判断质数 { if (y < 2) return 0; // 小于2肯定不是质数 for (int i = 2; i * i <= y; i++) // 只检查到sqrt(y) { if (y % i == 0)return 0; // 如果能整除，不是质数 } return 1; // 通过了所有检查，是质数 }这个函数很关键！检查范围是i * i <= y而不是i <= y，这就是刚才说的优化技巧。
第三部分：深度优先搜索（DFS）
void dfs(int x) { if (x == k + 1) // 已经选了k个数字 { int sum=0; for (int i = 1; i <= k; i++) // 计算选出的k个数字的和 { sum += b[a[i]]; // a[i]记录的是位置，b[a[i]]才是实际数字 } if (judge(sum)) cnt++; // 如果是质数，计数器加1 return; } for (int i = a[x - 1] + 1; i <= n; i++) // 关键！避免重复 { a[x] = i; // 记录选择第i个数字 dfs(x + 1); // 继续选择下一个数字 } }这是算法的核心！用深度优先搜索来生成所有组合。
解释一下关键点：
x参数表示当前正在选第几个数字当
x == k + 1时，说明已经选了k个数字，可以计算和并判断了循环中的
i = a[x - 1] + 1确保了每次选择的位置都比上一次大，这样就避免了重复组合
比如：选择了位置2的数字后，下一次就从位置3开始选，不会回头选位置1，这样就不会产生{1,2,3}和{2,1,3}这样的重复。
第四部分：主函数
int main() { cin >> n >> k; // 读取n和k for (int i = 1; i <= n;i++) // 读取n个数字 { cin >> b[i]; // 存储到b数组中 } dfs(1); // 从选第1个数字开始 cout << cnt; // 输出结果 return 0; }我踩过的坑
坑1：数组索引的选择
一开始还挺纠结：数组索引到底该从0开始还是从1开始？最后我选择了从1开始，因为这样更直观：
b[1]存储第1个数字b[2]存储第2个数字以此类推……
但要注意：循环条件也要相应调整，比如for (int i = 1; i <= n; i++)而不是for (int i = 0; i < n; i++)。
坑2：全局变量的初始化
在代码中，数组a[100010]是全局变量。这里有个小知识点：全局变量会自动初始化为0！
所以当我第一次调用dfs(1)时：
for (int i = a[x - 1] + 1; i <= n; i++) // 第一次：i = a[0] + 1 = 0 + 1 = 1这样就正确地从第1个位置开始选择了。
如果a是局部变量，就需要手动初始化为0了。
坑3：和的计算时机
我最初犯过一个错误：在每次递归时都计算部分和。但其实等到选满k个数字后再一次性计算更简单。
算法复杂度分析
这个算法的时间复杂度主要取决于：
组合数：C(n,k) 种选择方案
每种方案需要O(√sum)的时间判断质数
对于n≤20的情况，完全在可接受范围内。
总结
DFS是解决组合问题的利器，通过维护起始位置可以避免重复
质数判断有优化技巧，只需检查到√n
全局变量会自动初始化，这个细节很重要
代码调试要耐心，有时候小错误会导致大问题
