1. 项目概述与核心思路拆解“选数”这道题是很多信息学竞赛OI选手的“老朋友”了尤其是经历过NOIP全国青少年信息学奥林匹克联赛早期赛事的选手。题目本身描述非常简洁给定n个整数以及一个整数k要求你从这n个数中任选k个数相加问有多少种不同的组合其和是一个素数。初看之下这题似乎不难理解但真正动手实现尤其是对于刚接触算法竞赛的新手来说里面有几个关键点需要想清楚。首先它考察了两个核心算法思想的结合组合枚举与素数判定。组合枚举即从n个元素中不重复、不计顺序地选出k个的所有可能素数判定则是判断一个数是否为质数。题目将这两个看似独立的知识点串联起来形成了一个经典的“搜索数学”问题。为什么这道题经典因为它完美地充当了深度优先搜索DFS算法的入门练习题。DFS是一种用于遍历或搜索树或图的算法它会尽可能深地搜索树的分支。在“选数”问题中我们可以把“从n个数中选k个”的过程想象成在一棵决策树上进行探索每个数都有“选”或“不选”两种可能更常见的DFS写法是“选”或“跳过”我们需要探索所有恰好选择了k个数的路径并计算每条路径上数字的和。这个过程天然适合用递归实现的DFS来模拟。对于素数判定部分题目数据范围n≤20整数x_i ≤ 5×10^6意味着k个数的和可能非常大最大可达1亿。因此一个高效的素数判定算法至关重要。最朴素的从2遍历到sqrt(n)的试除法在这里是可行的也是本题最常用的解法。但这也引出了对算法效率的思考是本题的一个延伸价值点。所以解决这道题的总体思路非常清晰使用DFS递归地枚举所有C(n, k)种组合对每种组合计算其和然后用素数判定函数检查和是否为素数最后统计素数和的个数。接下来我们就深入每个环节看看具体怎么做以及有哪些需要注意的“坑”。2. 深度优先搜索DFS框架设计与实现DFS是解决本题的骨架。我们需要设计一个递归函数它能够系统地走过所有可能的k元组合。2.1 递归函数的状态定义首先要明确递归函数需要哪些参数来刻画当前的搜索状态。通常我们需要start或index当前从哪个位置开始考虑选择数字。这是避免重复组合如[1,2]和[2,1]被视为同一种的关键。我们规定每次只能从当前位置及之后的位置选取数字保证了组合的唯一性按原数组顺序。depth或count当前已经选择了多少个数字。当这个值等于k时我们就到达了一个“叶子节点”即找到了一种完整的组合需要对其进行处理检查和是否为素数。current_sum当前已选数字的总和。我们可以在递归过程中累加这样当到达叶子节点时current_sum就是最终的和无需再次遍历已选数字列表进行求和这是一个重要的优化。因此一个典型的递归函数签名可能是dfs(start, count, current_sum)。2.2 递归的流程与回溯递归过程遵循标准模式递归终止条件如果count k说明已经选够了k个数。此时current_sum就是这k个数的和。调用素数判定函数isPrime(current_sum)如果是素数则全局计数器ans加一。然后返回结束当前分支的搜索。递归主体枚举与选择如果还没选够count k我们需要从start到n这个区间内尝试选择下一个数字。这里有一个重要的剪枝优化如果剩余可选的数字数量n - start 1小于我们还需要选择的数字数量k - count那么即使把后面所有数都选上也不够k个这个分支可以直接放弃剪枝无需继续递归。做出选择与撤销选择回溯对于每一个可选的数字nums[i]i从start到n我们“选择”它。在代码中这体现为进行递归调用dfs(i 1, count 1, current_sum nums[i])。注意这里的i1作为新的start确保了下一个数字从当前数字之后开始选避免了重复。count和current_sum也相应更新。递归调用返回后意味着以nums[i]作为当前选择的所有分支都已经探索完毕程序会自动“回溯”到选择nums[i]之前的状态去尝试下一个可选数字nums[i1]。由于我们是通过参数传递状态而不是修改全局变量所以不需要显式的“撤销”操作这种写法更简洁安全。注意这里容易混淆“组合”和“排列”。题目要求的是组合即[1,2]和[2,1]是同一种。我们的DFS通过start参数确保了搜索顺序是单向的只往后看从而天然地生成了所有组合不会产生重复。如果去掉start参数每次递归都从0开始枚举就会生成所有排列导致大量重复计数。2.3 代码框架示例C风格伪代码int n, k; int nums[25]; int ans 0; // 全局答案计数器 // 素数判定函数后文详述 bool isPrime(int num) { ... } void dfs(int start, int count, int sum) { // 剪枝如果剩下的数全选也不够k个直接返回 if (count (n - start 1) k) return; // 终止条件已选满k个数 if (count k) { if (isPrime(sum)) { ans; } return; } // 从start开始尝试选择每一个数 for (int i start; i n; i) { // 选择 nums[i]进入下一层递归 dfs(i 1, count 1, sum nums[i]); // 递归返回后自动回溯尝试下一个i } } int main() { // 输入 n, k 和 nums 数组 dfs(0, 0, 0); // 从第0个数开始当前选了0个当前和为0 cout ans endl; return 0; }3. 素数判定算法的选择与优化在DFS枚举出每一个和之后我们需要快速且正确地判断它是否为素数。这是本题的第二个技术核心。3.1 基础试除法对于给定的整数num最直接的方法是试除法检查num是否能被2到sqrt(num)之间的任何整数整除。如果能则不是素数否则是素数。bool isPrime(int num) { if (num 2) return false; // 1和负数不是素数 if (num 2) return true; // 2是素数 if (num % 2 0) return false; // 排除偶数 int limit sqrt(num); // 只需要检查到平方根 for (int i 3; i limit; i 2) { // 从3开始只检查奇数 if (num % i 0) return false; } return true; }优化点特判小于2的数不是素数。2是唯一的偶素数。排除偶数在判断大于2的数时先判断是否为偶数可以立即筛除一半的情况。缩小范围只需检查到sqrt(num)。因为如果num有一个大于其平方根的因子那么必然对应一个小于其平方根的因子检查小因子即可。步长为2在排除了偶数后循环时i从3开始每次加2只检查奇数因子。对于本题的数据范围和最大约1亿sqrt(1e8) 1e4每次判定的循环次数最多一万次左右。而DFS枚举的组合数C(20,10)约为18.5万种在最坏情况下素数判定的总计算量大约在18.5亿次运算。这在现代计算机上配合优化通常能在题目要求的时间限制通常是1秒内完成但已经接近极限。因此这个基础的试除法是可行但非最优的。3.2 埃拉托斯特尼筛法埃筛的预计算优化如果我们能预先知道哪些数是素数那么在DFS过程中判断current_sum时就可以用O(1)的时间查表完成。这就是空间换时间的思路。埃筛的原理是假设所有数初始都是素数从2开始将每个素数的所有倍数标记为非素数。最终未被标记的数就是素数。const int MAX_SUM 1e8; // 根据题目最大和估计 bool isPrimeTable[MAX_SUM 1]; // 素数表true表示是素数 void sieve() { memset(isPrimeTable, true, sizeof(isPrimeTable)); isPrimeTable[0] isPrimeTable[1] false; int limit sqrt(MAX_SUM); for (int i 2; i limit; i) { if (isPrimeTable[i]) { for (int j i * i; j MAX_SUM; j i) { isPrimeTable[j] false; } } } }然后isPrime(num)函数就简化为bool isPrime(int num) { if (num 0 || num MAX_SUM) return false; // 边界检查 return isPrimeTable[num]; }优劣分析优势查询速度极快O(1)在需要大量素数判定的场景下优势明显。劣势空间开销大需要开辟一个大小为MAX_SUM1的布尔数组。对于最大和1亿的情况需要约100MB的内存bool在C中通常为1字节。这在一些内存限制严格的竞赛环境中可能无法通过。时间开销集中筛法本身有O(n log log n)的时间复杂度初始化需要一定时间。实操心得在“选数”这道题中通常不推荐使用埃筛。原因正是内存限制。竞赛题目的内存限制常见为128MB或256MB一个100MB的数组虽然可能勉强够用但加上程序其他部分的开销存在风险。而且本题的枚举量约18万次对于优化后的试除法来说是可以接受的。因此采用优化后的试除法是更稳妥、更通用的选择。埃筛更适合于需要频繁查询、且查询范围相对固定且可预知的场景。4. 完整代码实现与逐行解析下面给出一个整合了DFS和优化试除法的C完整代码并附上详细注释。#include iostream #include cmath using namespace std; int n, k; int nums[25]; // 题目说n20稍微开大一点 int ans 0; // 全局答案记录和为素数的组合数 // 优化后的试除法判断素数 bool isPrime(int num) { if (num 2) return false; if (num 2) return true; if (num % 2 0) return false; // 偶数不是素数除了2 int limit (int)sqrt(num); // 计算平方根只需检查到此为止 for (int i 3; i limit; i 2) { // 从3开始每次加2只检查奇数因子 if (num % i 0) { return false; } } return true; } /** * 深度优先搜索函数 * param start 当前从数组的哪个位置开始考虑选择 * param count 当前已经选择了多少个数字 * param sum 当前已选数字的总和 */ void dfs(int start, int count, int sum) { // 剪枝如果剩下的数字个数不足以凑齐k个直接返回 // 当前已选count个还需要 (k - count) 个。 // 从start到末尾(n-1)共有 (n - start) 个数字。 // 如果 (n - start) (k - count)则不可能成功剪枝。 if ((n - start) (k - count)) { return; } // 递归终止条件已经选择了k个数 if (count k) { if (isPrime(sum)) { ans; } return; // 返回上一层尝试其他选择 } // 从start位置开始尝试选择每一个数 for (int i start; i n; i) { // 选择nums[i]进入下一层递归 // 新的start是i1确保下一个数在当前数之后选避免重复组合 // count加1sum加上当前数字的值 dfs(i 1, count 1, sum nums[i]); // 递归返回后继续循环尝试选择下一个数即回溯 } } int main() { // 输入数据 cin n k; for (int i 0; i n; i) { cin nums[i]; } // 初始化搜索从第0个数开始当前选了0个当前和为0 dfs(0, 0, 0); // 输出答案 cout ans endl; return 0; }代码关键点解析数组与全局变量nums数组存储输入的n个数。ans作为全局变量在DFS中找到合法组合时自增。isPrime函数如前所述进行了特判、偶数和范围优化。dfs函数中的剪枝if ((n - start) (k - count)) return;这一行是重要的效率优化。它提前终止了那些“即使后面所有数都选上也不够k个”的无用分支减少了大量不必要的递归调用。递归调用dfs(i 1, count 1, sum nums[i])是核心。参数传递实现了状态的前进递归返回则意味着回溯。主函数读入数据从初始状态(0,0,0)开始调用DFS最后输出结果。5. 常见问题、调试技巧与扩展思考即使理解了算法在实现时也可能遇到各种问题。下面是一些常见坑点和解决思路。5.1 结果为什么是0或特别大结果为0首先检查素数判定函数isPrime。常见错误忘记处理小于2的数。循环条件写错例如for (i2; isqrt(num); i)应该用因为平方根本身也可能是因子。没有对输入数据进行验证确保DFS能正确遍历。结果特别大这几乎肯定是组合重复计数了。检查DFS函数是否保证了“组合”而非“排列”。关键点在于dfs调用中的start参数是否每次都在递增i1。如果错误地将start固定为0或一个不增长的值就会生成所有排列导致答案远大于正确值。5.2 递归深度过深导致栈溢出本题n最大为20k最大为20递归深度最大为20。这对于任何编程语言的递归栈来说都是安全的不会造成栈溢出。但这是一个好习惯在编写DFS时要心里有数递归深度是否在合理范围内通常几百以内是安全的上千就需要注意。5.3 如何调试DFSDFS的调试有时比较抽象可以尝试以下方法打印日志在dfs函数的开头打印当前的start,count,sum参数。在终止条件里打印找到的组合和判断结果。这样可以清晰看到递归的路径和决策。void dfs(int start, int count, int sum) { // 打印当前状态 // cout dfs called: start start , count count , sum sum endl; ... // 原有逻辑 if (count k) { // cout Found combination with sum: sum , isPrime? isPrime(sum) endl; ... } ... }使用小数据测试用手工可以计算的小数据如n4, k2数字很简单进行测试将程序输出与手工计算结果对比。使用IDE调试器设置断点单步执行观察变量变化和调用栈这是最强大的调试手段。5.4 时间复杂度的估算与优化思考时间复杂度主要来自DFS枚举和素数判定。枚举组合数为C(n, k)。最坏情况n20, k10时C(20,10)184756。对每个组合素数判定复杂度为O(√S)S最大约为1e8√S1e4。总计算量约184756 * 1e4 ≈ 1.85e9次运算。在现代CPU上经过优化如提前排除偶数勉强能在1秒左右完成。如果n和k更大这种方法就会超时。进一步优化方向记忆化本题中不同的组合可能产生相同的和。如果某个和已经被判定过是否为素数可以缓存结果。但考虑到和的范围很大到1亿用数组缓存不现实用map或unordered_map查询也有开销。在本题数据规模下收益不一定明显。更快的素数判定如米勒-拉宾素性测试这是一种概率算法速度极快适用于大数判定。但对于本题范围杀鸡用牛刀且实现稍复杂。改变枚举策略使用迭代而非递归递归的代码更清晰。对于组合枚举递归是最自然的表达。5.5 算法扩展如果n很大比如100k也很大怎么办当n达到100C(100,50)是一个天文数字暴力DFS完全不可行。这就进入了动态规划DP或折半搜索Meet-in-the-Middle的领域。但这已远超本题原意。原题“选数”的核心价值在于引导学习者掌握DFS解决组合枚举问题的基本范式并理解与基础数学知识的结合。最后这道“选数”题虽然基础但它像一块坚实的基石。熟练掌握它意味着你真正理解了DFS在组合问题中的应用以及如何将不同模块搜索、数学的代码清晰、高效地组织在一起。在竞赛或日常编程中这种“分解问题、组合算法”的能力远比死记硬背代码模板重要得多。