hello,大家好(普通到再普通不过的招呼),只是我的第一篇帖子，请大家多多点赞.(可以关注我吗awa)
话不多说，上正题~
关注链接:戳此关注~
每周一题之选数
选数
题目描述
已知 nnn 个整数，从中选出 kkk 个数，把选出的 kkk 个数相加得到和。求一共有多少种选法，使得选出数字的和是质数。
注意：选数只看集合，顺序无关。例如从 {1,2,3}\{1,2,3\}{1,2,3} 选 222 和 333，与选 333 和 222 算作同一种方案。
输入格式
第一行两个整数 n,kn,kn,k。
第二行 nnn 个整数 aia_iai 。
输出格式
输出一个整数，表示满足条件的方案总数。
数据范围
1≤n≤201 \le n \le 201≤n≤20，1≤k≤n1 \le k \le n1≤k≤n，1≤ai≤5×1061 \le a_i \le 5\times10^61≤ai ≤5×106
样例输入 1
> 样例解释：
* 3+7+11=213+7+11=213+7+11=21，不是质数
* 3+7+19=293+7+19=293+7+19=29，是质数
* 3+11+19=333+11+19=333+11+19=33，不是质数
* 7+11+19=377+11+19=377+11+19=37，是质数
合计 222 种方案。
样例输入 2
> 样例解释：
* 2+3=52+3=52+3=5，质数
* 2+4=62+4=62+4=6，非质数
* 3+4=73+4=73+4=7，质数
合计 222 种方案。
考点
回溯（深度优先搜索）、组合选取、素数判定，NOIP普及组真题难度。
提示
1. 做组合枚举，下标只能向后选取，避免重复统计。
2. 总和最大可达 10810^8108，无法使用埃氏筛，使用试除法判断素数。
3. 递归边界：选够 kkk 个数时，判断和是否为质数，统计答案。
题目思路
题意概括
从 nnn 个数字里选恰好 kkk 个（组合，不考虑顺序），统计有多少组，它们的总和是质数。
> 组合：选第0个、第1个 和 选第1个、第0个 是同一种，不能重复计数。
核心思路：DFS回溯枚举组合
DFS参数
* pos：当前处理到数组的下标，只能往后选，不回头，避免重复组合
* cnt：已经选了多少个数
* sum：已经选的数的累加和
递归逻辑
1. 边界1：已经选够 k 个数
判断 sum 是不是质数，如果是，答案 ans++，直接返回。
2. 边界2：pos走到数组末尾（全部遍历完）
直接返回，不能再选数。
3. 两种分支（每个数两种选择：选 / 不选）
* 不选当前 a[pos]：直接递归下一个位置 dfs(pos+1, cnt, sum)
* 选当前 a[pos]：递归 dfs(pos+1, cnt+1, sum+a[pos])
> 为什么pos+1：选过的下标不再回头，保证只会生成组合，不会生成排列。
素数判断要点
总和最大：20×5×106=10820 \times 5\times10^6=10^820×5×106=108，数组开不下筛法，只能用试除法。
* 小于等于1：一定不是质数
* 从2循环到 s\sqrt{s}s ，如果能整除，不是质数。
> 注意：sqrt() 返回double，循环条件建议写成 i*i <= s 避免浮点精度坑。
DFS补全片段
易错点
1. 递归下标错误，造成重复选数、重复统计方案
> 错误写法：dfs(pos, cnt, sum)
> 正确写法：dfs(pos + 1, cnt, sum)
> 说明：必须 pos+1，只能向后遍历，不能停留在当前下标，否则会重复选取同一个数字，把组合变成排列，答案偏大。
2. 递归边界判断顺序颠倒
> 错误：先判断 pos >= n，再判断 cnt == k
> 正确：先判断 cnt == k，再判断 pos >= n
> 说明：如果走到数组末尾时刚好选够k个数，先判断pos越界会直接return，漏掉本应统计的方案。
3. 素数判断使用 sqrt() 带来浮点数精度问题
> 错误：for(int i = 2; i <= sqrt(s); i++)
> 正确：for(int i = 2; i * i <= s; i++)
> 说明：sqrt返回double，大数会存在精度误差，i*i <= s 全部整数运算更安全。
4. 素数函数缺少 s <= 1 的判断
> 如果总和等于1，1不是质数，不做判断会错误算成质数。
5. sum整型溢出隐患
本题数据范围下 int 够用；如果题目数据放大，sum 需要改为 long long，否则总和溢出变成负数，素数判断全部出错。
6. 混淆组合与排列
不要往回访问前面的下标，一旦允许 pos 往前，就会出现 {3,7} 和 {7,3} 两套重复方案，ans结果翻倍。
7. 全局变量 ans 忘记重置
多组测试数据场景下，ans 要清零；本题只有单组输入，不会暴露这个bug。
时间复杂度
总共有 CnkC_{n}^{k}Cnk 种组合需要枚举。
本题 n≤20n \le 20n≤20，最坏情况为 C2010=184756C_{20}^{10}=184756C2010 =184756，组合数量不大，暴力DFS可以轻松通过。
每得到一组合法组合后，需要执行素数试除法。试除法时间复杂度为 O(S)O(\sqrt{S})O(S )，SSS 为选出数字的总和，最大为 10810^8108，S\sqrt{S}S 最大约 10410^4104。
整体复杂度：O(Cnk⋅S)O\left(C_{n}^{k} \cdot \sqrt{S}\right)O(Cnk ⋅S )。
AC完整代码（带详细注释）
总结
本题是NOIP普及组经典搜索题，核心考察DFS回溯求组合与素数判定。
1. 算法思想
使用深度优先搜索枚举所有选k个数的组合，每个数字有选、不选两种分支；通过pos+1只向后遍历下标，避免生成排列，保证只枚举组合。每当选够k个数，就判断总和是否为质数，统计合法方案。
2. 核心函数作用
* isPrime：试除法判断质数，优先使用i*i <= s避免浮点精度问题，记得处理小于等于1的特殊情况。
* dfs：回溯主体，三个参数分别记录当前下标、已选数量、累加和，两个递归边界分别处理选满k个数、遍历完数组。
3. 复杂度
时间复杂度 O(Cnk⋅S)O(C_{n}^{k} \cdot \sqrt S)O(Cnk ⋅S )，n≤20n\le20n≤20，组合数量不大，暴力搜索完全可以通过。
4. 高频坑点
* dfs递归一定要pos+1，不能停留在原下标；
* 边界顺序：优先判断选够k个，再判断下标越界；
* 素数判断注意1不是质数，规避sqrt浮点数误差；
* 数据规模变大时sum要改用long long防止溢出。
5. 拓展
如果n继续增大，暴力DFS会超时，可以使用动态规划优化；本题数据范围小，回溯是最简单直观的解法。
最后感谢您的阅读，动动你的金手指给个赞吧~
