刷算法题的人大概率对 P1036 这个编号不陌生。它就是 NOIP 2002 普及组的那道“选数”一道看起来平平无奇、却让很多初学者第一次感受到“会暴力不一定能 AC会枚举才是入门”的题目。这道题放在今天来看难度不算高但它的核心思想——组合枚举、DFS 搜索、素数判断——几乎是所有信息学竞赛选手绕不开的基本功。如果你正在准备 CSP-J、NOIP 普及组或者刚开始学深度优先搜索这道题绝对值得认真做一遍。哪怕你已经工作了回头再看这道题也能帮你快速理清“递归枚举组合”这件事的本质。我最初做这道题时其实踩了不少坑也花了不少时间才弄明白为什么全排列能过但思路不对为什么直接套 DFS 会重复计数为什么素数判断的边界总是写错。这篇文章就围绕这几个问题把题目从暴力思路、DFS 组合枚举、优化再到调试技巧完整拆开来讲清楚希望能帮你少走弯路。1. 题目到底在考什么1.1 原题复述与核心规则题目原意很简洁已知 n 个整数 x1, x2, ..., xn以及一个整数 kk n从 n 个数字中任选 k 个数字相加问一共有多少种不同的和为素数。数据范围是硬约束n ≤ 20k n每个整数 xi ≤ 5000000。举个例子输入是 4 个数字 3、7、12、19k 3那么需要从这 4 个数里选 3 个求和得到四种组合3 7 12 22不是素数3 7 19 29是素数3 12 19 34不是素数7 12 19 38不是素数所以答案是 1。这个例子很经典它把“组合”“求和”“素数判断”三个环节全串起来了。很多人一开始会误以为这是一个排列问题觉得五个数随便调换顺序也算不同选法但实际上题目问的是“选数”是典型的组合问题——选择集合不看顺序。1.2 数据范围决定了算法方向看到 n ≤ 20很多人第一反应是“直接暴力枚举”。这个思路本身没错但关键在于怎么枚举。所有子集的规模是 2^n当 n 20 时大约是 100 万级别这其实也完全可以在 1 秒内跑完。而所有组合数的规模是 C(n, k)最坏情况出现在 k n/2 时C(20, 10) 184756也就是大约 18 万种组合。这比遍历全子集还要小一个数量级。所以这道题真正考察的点不是“能不能枚举”而是“你会不会用程序高效、不重复地枚举组合”。如果只会写“递归枚举所有子集再判断 popcount”那当然也能过但你会失去一次学习标准组合枚举写法的机会。竞赛中更常见的做法是用带起始位置参数的 DFS一次递归只向后选数从根源上避免重复组合的产生。这种方式不仅代码简洁效率也更高而且很容易扩展到“枚举组合之后还要对组合做各种统计”的题目里。2. 组合枚举的核心思路为什么是 DFS2.1 排列、组合与去重的本质区别先理清一个概念排列permutation和组合combination的区别。排列关心顺序(1, 2, 3) 和 (3, 2, 1) 在排列中是两种但在组合中是同一种。如果我们写一个普通的 DFS每次递归都尝试从所有数字里选一个填入当前位那生成出来的是排列不是组合。比如选 3 个数字时它会同时生成 (3, 7, 19) 和 (19, 7, 3) 这样内容相同的组合。因为题目只统计“和为素数的组合有多少种”这两种会被当成两个不同方案来计算答案就错了。避免重复有两种常见做法。一种是用哈希表或集合来记录已经出现过的组合每生成一个组合就插入 set最后统计 set 的大小。这种办法能过但每次插入集合都会带来额外的开销而且需要额外处理如何把一组数字序列化成唯一的键。另一种更漂亮的方案就是控制递归的“搜索范围”每次从上一个选中数字的下一个位置开始选这样就强制了组合内元素的下标严格递增天然不会重复。这也是竞赛圈里学 DFS 时最基础、最常用的“组合枚举模板”。2.2 带 start 参数的搜索状态设计DFS 函数可以设计成这样dfs(step, start, sum)其中 step 表示当前已经选了多少个数字start 表示这一层可以从哪个下标开始选sum 表示当前已选数字的总和。递归的每一层从 start 循环到 n - (k - step)也就是保证“剩余可选数字的数量 ≥ 还需要选择的数字数量”。这个上界的限制是一个小幅剪枝但它不是为了性能——毕竟组合数量本来就不大——而是为了培养写搜索时的边界意识。当 step 达到 k 时说明我们已经选够了 k 个数字此时只需要判断 sum 是否是素数如果是答案计数加一然后 return。这一段逻辑就是整道题的骨架理解了它组合枚举类的题目基本就能拿下八成。2.3 为什么不用 next_permutation 或子集枚举有人会问既然 n 最大 20直接用子集枚举不行吗用位运算遍历 0 到 (1 n) - 1统计每个子集的 1 的个数如果等于 k就把对应元素求和判断素数。确实可行。但问题是这种写法在 n 更大一点比如 n 30 时2^30 约等于 10 亿就完全跑不动了。而 DFS 组合枚举的复杂度是 C(n, k)在 k 接近 n/2 时虽然还是很大但它不会像 2^n 那样指数爆炸得那么快而且通过 start 参数可以天然规避重复组合不需要额外的判重逻辑。再者从学习价值来看next_permutation 是 STL 提供的现成函数你调它不需要理解内部实现但竞赛题里更多时候需要你“现场造轮子”。DFS 组合枚举正是这类轮子中最基础的一个。掌握了它后面遇到“从 n 个数中选 k 个数满足某种条件”的变体题你都能直接套模板不会慌。3. 完整实现与关键细节3.1 一份可运行的 C 参考代码我在这里给出一版我常用的写法用的是 C因为竞赛中这语言最通用。你完全可以根据自己熟悉的语言改写。#include bits/stdc.h using namespace std; int n, k, ans 0; int a[25]; bool isPrime(int x) { if (x 2) return false; // 用 i*i x 而不是 i sqrt(x)避免浮点误差 for (int i 2; i * i x; i) { if (x % i 0) return false; } return true; } // step: 当前已选个数 // start: 本轮选择起点下标 // sum: 当前已选数字之和 void dfs(int step, int start, int sum) { if (step k) { if (isPrime(sum)) ans; return; } // 剪枝保证剩余数字足够 for (int i start; i n - (k - step); i) { dfs(step 1, i 1, sum a[i]); } } int main() { cin n k; for (int i 1; i n; i) cin a[i]; dfs(0, 1, 0); cout ans endl; return 0; }这段代码里数组下标从 1 开始这个习惯在竞赛里很常见可以避免 DFS 边界处理时出现“减一加一”的混乱。注意 for 循环的条件 i n - (k - step)当 step 0 时循环上界是 n - k当 step k - 1 时循环上界是 n - 1。也就是最后一层至少要从 n - 1 开始选保证还剩下一个数可以选。如果你写成 i n其实也能过因为 dfs 内部 step k 就先返回了但写上这个上界能让你更清楚递归的边界。3.2 素数判断的边界与性能素数部分的判断看似简单实际容易出问题的地方不少。首先x 1 不是素数x 2 是素数这两个特殊情况必须处理。很多新手写 isPrime 时直接从 i 2 开始循环然后返回 true结果会把 1 判成素数导致答案偏大。其次循环终止条件用 i * i x 有个潜在的整数溢出问题当 x 很大时比如接近 int 上限的 2^31 - 1i * i 可能会溢出变成负数从而形成死循环或错误判断。虽然本题 xi ≤ 5000000sum 最大也就一亿远没到 int 上限不会出问题但这是一个很好的习惯养成点。更稳妥的方式是写成 i x / i这样绝对不会溢出。最后性能上sum 最大约为 20 × 5000000 100000000sqrt(100000000) 10000每判断一次素数最多循环一万次。组合数最多约 18 万两者相乘大约是 18 亿次操作看着吓人实际上因为素数判定的平均循环次数远小于最坏情况大多数和都是小因子先暴露实际运行时间完全在可接受范围内大概几十毫秒。3.3 递归过程的模拟与理解为了帮助理解我用刚才的例子跑一遍递归。n 4k 3数字是 3、7、12、19。dfs(0, 1, 0) 进入第一层循环 i 1 到 2。i 1 时选择 a[1] 3调用 dfs(1, 2, 3)。第二层循环 i 2 到 3。i 2选择 a[2] 7调用 dfs(2, 3, 10)。第三层循环 i 3 到 4。i 3选择 a[3] 12sum 22step 到达 k判断 22 不是素数。i 4选择 a[4] 19sum 29判断是素数ans。回到第二层i 3选择 a[3] 12调用 dfs(2, 4, 15)。第三层只有一个 i 4选择 19sum 34不是素数。回到第一层i 2选择 a[2] 7调用 dfs(1, 3, 7)。之后组合为 7 12 19 38不是素数。全过程恰好遍历了所有 4 种组合没有重复没有遗漏这种“沿着下标顺序走”的设计就是组合枚举的精髓。4. 常见错误与调试技巧4.1 新手最容易踩的几个坑第一个坑是 DFS 参数设计混乱。有些人会把 start 写成从 0 开始数组下标又用 0 开始结果 start 1 和 i 1 弄混导致递归时选了同一个元素两次或者漏选元素。我的建议是统一一套约定数组从 1 开始start 从 1 开始递归传入 i 1。这样代码读起来很顺畅不容易错。第二个坑是剪枝条件写反了。有人会把循环上界写成 i n也不影响正确性但如果加上了上界就必须写对。你可以这样记当前已经选了 step 个还需要选 k - step 个为了能选够数当前这一位最晚可以从第 n - (k - step) 1 个位置开始选但因为我们用的是 a[i] 且下标从 1 开始所以循环条件写 i n - (k - step) 是精确的。如果写成 i n - (k - step)就会漏掉最后一个位置的组合。第三个坑是 isPrime 函数没有处理 x 1。很多题目数据里会包含 1如果数字里有 1那么选出来的和为 1 时按错误写法会被判成素数从而多计数。这个坑在平时练习时不一定能碰到但一旦碰到排查起来非常痛苦。4.2 测试数据与输出验证我通常建议用几组小数据来验证程序。第一组n 1k 1输入 2。结果应为 1因为 2 是素数。如果输出 0说明 isPrime 里对 2 的处理有问题。第二组n 5k 3输入 1 2 3 4 5。所有组合如下123 6不是124 7是125 8不是134 8不是135 9不是145 10不是234 9不是235 10不是245 11是345 12不是正确答案是 2。如果你程序输出不是 2说明组合枚举或者素数判断里一定有问题。第三组n 4k 2输入全是负数比如 -1 -2 -3 -4。选两个数之和最小是 -7最大是 -3没有素数答案应该是 0。这组数据用来验证负数情况下的素数判断是否正确。注意 isPrime 里要先判断 x 2 返回 false负数就不会进入循环直接判为 false。4.3 几个实用的调试技巧第一在 dfs 函数的入口打一行调试输出打印 step、start、sum 和当前选的数字序列。这样可以非常直观地看到递归树的走向定位重复或遗漏的问题。第二用一个全局变量记录已经生成的组合数量然后和一个用数学公式手算出的 C(n, k) 做对比。如果递归生成的总组合数不等于 C(n, k)那说明枚举逻辑有 bug而不是素数判断的问题。这个方法能把“组合枚举错误”和“素数判断错误”快速分离。第三本地测试时用几组随机数据再用最暴力的 next_permutation set 去重写法作为基准程序两相对拍。如果两个程序在随机数据上的结果一致那你基本可以放心了。对拍是竞赛里非常实用的一种验证手段。5. 题目之外算法思想的延伸5.1 从“选数”到“背包型 DFS”的变式P1036 是组合枚举类题目的模板题很多题都是它的变体。比如同样是“从 n 个数里选 k 个”但条件是“和不超过某个上限”那就是一个带约束的 DFS只需要在递归时判断 sum 是否已经超过上限超了就剪枝。再比如如果要求输出所有满足条件的组合而不只是个数那么只需要在 step k 时打印组合序列而不是简单地 ans。这类题型的核心都是 DFS 的状态设计当前选到第几个、已经选了几个、当前累计值。这个三元组几乎可以套用到无数题目中。可以说P1036 是“把 DFS 状态设计搞明白”的一把钥匙。5.2 对复杂度与算法选型的思考这道题数据范围小暴力 DFS 足以应对。但如果你遇到了 n 50、k 25 这种组合数爆表的题目DFS 就行不通了那就需要用到折半搜索Meet in the Middle或者动态规划。从这个角度说P1036 也给你提了个醒看到“选 k 个”的问题要先估算组合数的规模再决定用什么算法。我个人的习惯是拿到题先算 C(n, k)。如果这个值在百万级别DFS 没问题如果到了千万级别就要看能不能剪枝如果到了亿级别基本就得另找思路了。这是一种很朴素的复杂度直觉靠刷题能慢慢培养出来。另外这道题也让我养成了一个好习惯写素数判断时永远先处理 x 2然后用 i x / i 作为循环条件不依赖 sqrt 函数。这个习惯在后来的很多题目里都帮了我大忙因为很多题目的答案可能大到接近 long long 上限判断素数时稍不注意就会溢出。5.3 一道题三重训练回头看这道 P1036它表面上是一道“选数数素数”的问题实际上是一道集组合枚举、DFS 递归、数学判断于一体的综合基础题。组合枚举训练的是“如何让程序按顺序、不重复地遍历组合”DFS 训练的是“如何设计递归状态与参数”素数判断训练的是“边界处理与代码习惯”。这三样东西在你往后刷题的过程中会反复用到。真不是夸张我后来做过的许多搜索题、记忆化搜索题、状压 DP 题初始思路都是从这道题演化出来的。如果你现在正被这道题折磨别急慢慢把递归过程画出来理解每一步的 start 和 sum 变化很快就能顿悟。一旦掌握了这种“从上一个位置之后开始选数”的思路你会发现这类组合枚举题都是同一个套路之后做得多了看到“选 k 个”“和为多少”“求方案数”这些字眼脑子里就会自动跳出 DFS 模板。最后再分享一个我实际做这道题时学到的小技巧如果你不确定自己写的 DFS 到底枚举了多少种组合可以在递归到 step k 时用计数器加一最后输出计数器的值看它是否等于 C(n, k)。这个验证方法我屡试不爽能帮你快速定位问题是出在枚举逻辑上还是出在素数判断上。也建议你试试在纸上手写一遍 n 5、k 3 的递归树把每个节点的 start 和 sum 都标出来这对理解 DFS 组合枚举有奇效。