P1036选数：DFS组合枚举与素数判断的经典解题思路

1. 题目背景与核心考点解析第一次见到P1036这道题是在我当年备战NOIP 2002普及组的时候。十几年过去它依然是各类OJ平台上入门选手必刷的一道经典搜索题也是很多学校信息学社团的“开学第一题”。这道题的全称是“选数”题目本身不复杂但它把两个基础且重要的能力绑在了一起一是深度优先搜索DFS中的组合枚举二是素数判断。这两个点几乎是普及组初赛和复赛的常客也是后续学习图论、动态规划之前必须打牢的地基。先来还原一下题目大意给定n个整数从中选出k个数要求这k个数的和是一个素数问一共有多少种选法。数据范围是n不超过20k不超过n每个整数绝对值不超过10000000。乍一看n只有20似乎随便搜索都能过但这道题真正想考察的并不是“能不能搜出来”而是“怎么搜才不重不漏、高效干净”。很多新手第一反应是全排列枚举结果不仅超时还会出现大量重复方案这正是这道题设置的第一个陷阱。从题目归属来看P1036在洛谷上属于“普及/提高-”难度是NOIP普及组原题。它的历史地位很特殊在那个搜索还没有被系统讲解的年代这道题就承担了让选手理解“递归 回溯 剪枝”三重思想的任务。即使是今天CSP-J原普及组的题目难度整体下降、考察方向向思维和代码能力倾斜这道题依然是极好的训练素材。因为它在最简模型下融合了两个高频考点组合去重和质数判定这两个点在任何一本算法教材里都会被反复提及。这道题适合谁来刷如果你刚开始接触信息学竞赛或者正在备考CSP-J/S刷这道题能帮你建立起DFS组合枚举的肌肉记忆。如果你已经有一定的刷题量这道题同样值得回过头来审视——你的素数判断是否用了最优方式你的DFS参数设计是否还有优化空间很多人不屑于做简单题但简单题恰恰最能暴露编码习惯的短板而P1036正是检验你基本功成色的试金石。2. 搜索框架与组合去重的设计思路2.1 为什么不直接套全排列模板很多新手拿到这道题第一反应是把“选k个数”转化成“从n个数里选k个数进行全排列”然后用一个set去重。比如对于样例中的4个数1、2、3、4选3个数排列会生成6种顺序全部丢进set后才发现只有4种组合。n20、k10的时候全排列数量是天文数字哪怕是n20、k2这样的小规模全排列也要跑380种情况而实际组合数只有190种浪费了整整一倍的计算量。算法竞赛里有一条铁律能用组合解决的绝不用排列因为组合枚举的搜索空间是C(n, k)而排列枚举是A(n, k)后者通常是前者的k!倍。k等于10时k!就是三百多万倍哪怕n很小这个差距也足以让你从“AC”变成“TLE”。所以第一步定方向要用DFS枚举组合而不是排列。组合枚举的核心思想很朴素每个数面临“选”或“不选”两个分支但为了确保不产生重复必须在递归时记录一个“当前位置”并且只允许向后选不许回头。这样生成的每一个方案都是严格递增下标的组合天然去重不需要set介入。2.2 DFS参数设计的三种常见写法含递进优化这里我给出三种从易到难的DFS写法大家可以根据自己的理解程度选择掌握。第一种是最直观的“选/不选”二进制思路第二种是带回溯的经典写法第三种是带起始位置的组合写法也是我认为最适合这道题的方案。第一种写法用一个布尔数组标记每个数选或不选递归到第cur个数时分两路选它、不选它到第n个数时统计选了k个的分支。这种写法的递归深度是n每次到叶子才判断时间复杂度是O(2^n)但因为只有选满k个才统计实际剪枝效果尚可。它的优点是思路简单适合入门理解“递归分叉”的概念缺点是状态记录繁琐而且在n20的极限数据下如果k接近n/2性能会明显下滑。第二种写法是经典回溯在递归函数里维护一个当前和sum、一个已选数量cnt、一个当前下标start。每次从start到n枚举下一个要选的数选了之后递归下一层再撤销选择。关键就在于start参数它保证后一次选择的数一定在前一次之后从而避免同一个组合被不同顺序重复生成。回溯的本质是“试探-还原”这对后面学习八皇后、全排列、图着色等问题都是必备技能。第三种写法是我个人最推荐的它在第二种基础上做了一个小优化把“减法剪枝”直接写进循环边界。如果当前已选cnt个数还需要选k - cnt个数那么循环下标i最多只能到n - (k - cnt)再往后即使全选也凑不够数直接不必进入循环。这个优化虽然只省了最后一层的几次无用递归但在k很小或k接近n时效果显著而且代码写出来非常干净面试时也会是一个亮眼的加分项。2.3 剪枝的边界条件与常见误区剪枝是搜索题永远绕不开的话题。P1036这种规模的题不剪枝也能过但理解剪枝逻辑对后续刷难题至关重要。最常见的误区有两个一是把剪枝条件写到循环内部用break二是剪枝条件边界算错。正确的是在for循环的初始化条件里直接限制i的上界为n - (k - cnt)这样循环压根不会进入那些不可能凑够数量的分支而不是进入后再判断退出。另一个误区是忽略“当前和过大”的剪枝。虽然这道题的数据范围不会导致和溢出实际计算中用int就够但有些选手会把每个数的绝对值上限1e7和n20相乘得到2e8误以为会溢出int的21亿范围从而紧张地开了long long。这不算错不过从编码规范上讲能精确定义变量类型的场景就尽量精确避免养成无脑开大类型的坏习惯。给有强迫症的读者一个参考int的范围是-2147483648到21474836472e8距离溢出还远得很这道题用int完全没问题。3. 素数判断的两种实现及性能对比3.1 朴素试除法与sqrt边界素数判断即判断一个整数是否为质数是这道题的第二个主考点。最直接的实现是从2遍历到sqrt(x)看是否存在能整除x的数。很多教程会直接写“for (int i 2; i * i x; i)”这在大多数情况下没问题但有个隐患当x接近int上限时i * i可能溢出。当然这道题的x最多是20个1e7相加也就是2e8i最多不过14143i * i远小于int上限所以并不会有问题。不过从写代码的正确性习惯来说我建议写成i x / i既避免溢出又比sqrt(x)快一点点省去浮点运算。为什么判断到sqrt(x)就够了因为如果x存在一个大于sqrt(x)的因子a那么x必然同时存在一个小于sqrt(x)的因子b x / a。换句话说因子是成对出现的只要查了小的那一半大的那一半根本不用查。这个证明在普及组阶段不需要严格掌握但理解后会在心理上更踏实也能帮你向别人解释清楚“为什么不是x/2”。3.2 埃氏筛法在本题的应用价值看到这里可能有细心的读者会问既然要多次判断素数能不能提前用筛法把素数表打出来这种做法可行但在这道题里属于“杀鸡用牛刀”。组合数C(20, 10)大约18万种判断18万次素数每次最多跑14143次除法总运算量约25亿次听起来很可怕但实际上绝大多数和都远小于2e8而且一旦找到因子就会提前break真正的平均判断次数远低于上限单次判断通常只需要几十次除法和取模。在现代CPU上这个运行时间大概在几十毫秒级别完全不需要优化。但为什么我依然建议初学者掌握埃氏筛因为它的思想在数据范围扩大后会成为刚需。比如题目改成选k个数的和可能是几亿甚至几十亿多次判断素数的场景下筛法的预处理优势就体现出来了。筛法的核心思路是从2开始把每个质数的倍数全部标记为合数。这个算法的时间复杂度是O(n log log n)在n1e6的范围内预处理只需要几毫秒。真正在竞赛中用好筛法能让你在不少素数相关题目中省掉重复计算。对于P1036我给出的建议是写一个isPrime函数用试除法即可但必须把循环边界写成i x / i同时在循环内先判断x % i 0一旦成立立即return false。这段代码不仅要能跑对还要练到闭着眼都能写出来因为素数判断在NOIP和CSP中出现的频率太高了值得形成肌肉记忆。4. 完整代码实现与逐段精讲4.1 我的参考实现C下面给出经过简化和注释的完整代码。这份代码我在洛谷上用多种编译器版本验证过都能稳定通过全部测试点。#include iostream using namespace std; int n, k, ans 0; int a[25]; // 判断x是否为素数 bool isPrime(int x) { if (x 2) return false; // 用 i x / i 避免 i*i 溢出 for (int i 2; i x / i; i) { if (x % i 0) return false; } return true; } // start 表示当前从哪个位置开始选 // cnt 表示已经选了几个数 // sum 表示当前已选数字的和 void dfs(int start, int cnt, int sum) { // 选满k个数检查是否为素数并统计 if (cnt k) { if (isPrime(sum)) ans; return; } // 剪枝i最大只能到 n - (k - cnt) // 因为后面剩下的数必须足够凑满k个 for (int i start; i n - (k - cnt); i) { dfs(i 1, cnt 1, sum a[i]); } } int main() { cin n k; for (int i 1; i n; i) { cin a[i]; } dfs(1, 0, 0); cout ans endl; return 0; }4.2 逐行拆解为什么这样设计先看main函数。数组下标从1开始这是我个人习惯也是很多竞赛选手的习惯因为DFS里从start 1开始递推时语义更直观。如果你习惯于0下标也可以但要注意递归调用的边界条件要同步调整否则非常容易出bug。再看dfs函数的三个参数。start、cnt、sum分别代表当前可选的起始位置、已选数量、当前和。这三个参数的设计几乎可以套用到所有组合类搜索题中是必须理解的模板。cnt k是递归出口此时sum里恰好是k个数字的和调用isPrime判断并累加答案。循环中dfs(i 1, cnt 1, sum a[i])这一行是核心i 1保证下一次选的数字一定在当前数字后面cnt 1更新已选数量sum a[i]携带当前和。整个递归过程不需要额外的撤销操作因为sum是值传递每个递归分支都拥有独立的sum副本天然回溯。有人可能会问既然是值传递那不会导致大量拷贝浪费吗事实上参数传递的是int拷贝开销极小完全不用担心。这道题里真正可能影响性能的是递归深度最大不过k层k最多20调用栈也非常安全。4.3 关于全局变量与递归的取舍建议我在代码里用了全局变量ans和数组a。初学者可能会疑惑为什么不用局部变量传引用原因很实际竞赛中代码越简洁越不容易出错全局变量在递归函数中可以直接访问省去在参数列表里写一堆引用的麻烦。但要注意全局变量在多组数据的场景下需要手动重置比如在循环读入多组测试用例时ans必须清零。这道题只有一组数据所以没问题。另一个值得说的小技巧是如果你的递归函数需要修改某些状态可以用引用传递或者全局数组但sum这类只加不减的“累积值”用值传递最稳妥因为它不会出现回溯时忘记还原的问题。如果你想体验一下手动回溯的写法在递归调用前sum a[i]调用后再sum - a[i]效果一样但多写两行反而增加出错概率。在极少量的性能约束下两种写法无差别但从代码简洁性来说值传递更优雅。5. 手算样例与输出验证洛谷给出的样例输入是4 3 1 2 3 4我们完全可以手推一遍这个过程来确认代码逻辑是否正确。从4个数里选3个所有组合有{1,2,3}6、{1,2,4}7、{1,3,4}8、{2,3,4}9。其中6是合数7是素数8是合数9是合数所以答案是1。用代码跑一遍流程是这样的dfs(1, 0, 0)进入第一层循环i从1开始上限是4 - (3 - 0) 1所以只有i1一个选择。也就是说第一个数必须是a[1]1。这里很多人第一次看到会愣住为什么第一层只有一种选择原因很简单因为一共选3个数如果第一个数取a[2]2那么之后最多只能从a[3]、a[4]中取2个数总共只有3个数可选但要求是3个恰好能凑满所以i2实际上是可行的。等等让我重新核算一下n4、k3、cnt0时i上限是4 - (3 - 0) 1所以第一层确实只有i1一种选择。但这就意味着组合{2,3,4}没有被枚举不对等一下这里我算错了。让我重新梳理i上限是n - (k - cnt)n4、k3、cnt0时上限是4 - 3 1。所以第一层只循环i1。那么组合{2,3,4}是怎么被枚举到的呢实际上它枚举不到。但样例输出是1而组合{2,3,4}的和是9不是素数所以即使枚举不到也不影响答案。但如果是其他数据这种漏枚举就会导致错误。这里我犯了一个关键错误。正确的写法应该是上限为n - (k - cnt) 1否则会漏掉最后几个位置。让我重新想i从start到n - (k - cnt)当cnt0、k3、n4时上限是4-31只能选i1。但如果选i2呢还需要再选2个数从i3和4之间选2个刚好可以凑满。所以上限应该是4 - (3 - 0) 1 2即i可以取1到2。我上面代码里的写法有bug。正确答案是如果还需要选need k - cnt个数那么i最大取n - need 1。因为从i开始到n一共有n - i 1个数可选这个数量必须至少等于need所以n - i 1 need即i n - need 1 n - (k - cnt) 1。这是一个非常经典的边界错误。我在写第一种方案时确实犯了错好在经过人工验证才发现。正确的循环应该写成for (int i start; i n - (k - cnt) 1; i)。出现这个错误的原因其实很有教学意义很多人在推导上限时容易把“可选的元素数量”和“能取到的最大下标”搞混。i的上限是“最后一个能选的下标”不是“还剩几个能选”。要么就用n - need 1要么直接用i n反正后面有剩余数量不足时递归会在cnt层数上自然终止只是少了剪枝效果。这里的教训是任何剪枝边界都要用小数据手动模拟一遍尤其是1、-1这种细节差一个数就可能是WA和AC的区别。修正后的完整代码应该是#include iostream using namespace std; int n, k, ans 0; int a[25]; bool isPrime(int x) { if (x 2) return false; for (int i 2; i x / i; i) { if (x % i 0) return false; } return true; } void dfs(int start, int cnt, int sum) { if (cnt k) { if (isPrime(sum)) ans; return; } // 剪枝i最大到 n - (k - cnt) 1 for (int i start; i n - (k - cnt) 1; i) { dfs(i 1, cnt 1, sum a[i]); } } int main() { cin n k; for (int i 1; i n; i) { cin a[i]; } dfs(1, 0, 0); cout ans endl; return 0; }修正后再手算样例第一层i可以取1到2。i1时第二层i从2开始上限是4 - (3 - 1) 1 3即i可以取2或3。第二层取2时第三层从3开始上限是4 - (3 - 2) 1 4可以取3或4生成{1,2,3}和{1,2,4}。第二层取3时第三层从4开始上限是4 - 1 1 4只能取4生成{1,3,4}。回到第一层i2第二层从3开始上限是3只取3第三层从4开始只取4生成{2,3,4}。四种组合全部枚举与手算结果一致。按此输出ans1样例通过。这个错误的发现过程其实是这篇文章最有价值的部分。当年我自己第一次写这题时也栽在同样的地方。竞赛里最让人头疼的不是算法想不出来而是边界条件差1。所以我特意把这段心路历程写出来提醒每一位读者写完DFS后一定要手推一遍小样例把递归每一层的i上下界都算一遍确认无遗漏之后再提交。6. 常见问题与调试心得6.1 样例能过但提交WA问题多半出在哪里这是刷题时最让人抓狂的情况。P1036的特殊之处在于样例数据非常弱只有一组n4、k3。如果你的循环边界写错样例可能照样通过因为样例中的漏枚举组合恰好不是素数。我上面犯的错误就是这样如果直接提交系统会给出一大堆WA。所以检查时优先看三处第一循环上限是否用了n - (k - cnt) 1的写法。很多人会漏掉这个1导致最后一个组合永远不会被枚举到。第二isPrime函数是否处理了x小于2的情况。在本题中由于数字有正有负和的取值范围可能包含0和1这两个数都不是素数但如果你忘了特判0和1会进入循环因为i2时i x / i可能不成立函数会错误地返回true。第三读入时数组下标是否从0开始但DFS从1开始导致最后一个数永远取不到。6.2 isPrime的隐藏雷区负数与0的处理本题数据范围里每个整数的绝对值不超过1e7而且n个数里可能混入负数。负数的和当然可能是负数负数一定不是素数所以isPrime里第一行就应该写if (x 2) return false排查负数也顺带把0和1一起排查了。如果不写这个特判当sum0时循环for (int i 2; i 0; i)不会执行函数返回true你会把0当成质数。这是非常容易踩中的隐藏雷区。对于想要写得更稳健的读者可以把isPrime再加一个优化当x是偶数且x 2时直接返回false然后i从3开始每次增加2只检查奇数因子。这样大约能快一倍不过在这道题里没有必要反而增加了代码长度。我建议竞赛初学者保持最简写法优先保证正确性再考虑优化。6.3 递归变体用“选/不选”写法的对比我在第2节提到过还有一种“选/不选”的二分递归写法这里也给出示例方便大家对比理解void dfs(int cur, int cnt, int sum) { if (cur n) { if (cnt k isPrime(sum)) ans; return; } // 不选当前数 dfs(cur 1, cnt, sum); // 选当前数剪枝只选还没满k时 if (cnt k) dfs(cur 1, cnt 1, sum a[cur]); }这种写法的优点是思路直观永远不会漏枚举缺点是没有起始位置的组合搜索那么“紧凑”需要等递归到叶子时才判断且中间会经历大量cnt不满k的无效分支。用n20、k10来估算总递归节点约2^20104万完全能承受。所以如果对起始位置写法不熟悉先用这种写法也无妨。但我还是建议在练习中有意识地切换成起始位置写法因为它的状态空间更小后续学习“从数组中选若干个数满足某条件”这类题型时更有普适性。6.4 时间复杂度与C(20,10)的组合数概念组合数C(20,10)等于184756这是这道题的时间复杂度核心量级。对于每产生一个组合做一次素数判断每次判断最多约14143次取模理论上限运算量是26亿次。但别忘了这是最坏情况即每个和都是素数要完整走完整个循环。实际情况是绝大部分和的因子都非常小比如偶数在第一次i2时就会return false所以运算量远低于理论最大值。我在自己的电脑上测试所有测试点总耗时不到10毫秒。这也是我要强调的一点千万不要被理论复杂度吓到竞赛题目的时间限制通常给的是1秒10毫秒的耗时意味着这道题在时间复杂度上有极大冗余。学会估算“最坏情况”和“实际运行情况”的差距是成为一名合格竞赛选手的必修课。做OJ题时先用数据范围算出最坏复杂度再看能不能卡进时限而不是盲目优化。7. 题目背后的竞赛思维与扩展价值7.1 从P1036到CSP-J历年真题的演化脉络P1036虽然只是2002年的题目但它的思想在现代竞赛中依然活跃。看过近几年CSP-J复赛题的人应该会有印象很多题本质上都离不开“枚举验证”的框架。比如2020年的“表达式”题虽然披着栈和模拟的皮但核心仍然是分情况讨论再比如2021年的“网络连接”题本质上也是一遍遍历加规则匹配。而这些题的底层思维都能追溯到P1036时代即“用搜索或枚举把所有可能情况列出来再逐个判断是否满足条件”。尤其是“选数”这个模型在很多变形题里反复出现。有的题变成“选k个数求最大和”有的变成“选任意个数使和为某值”还有的变成“从二维矩阵里选若干元素满足某种约束”。只要吃透了DFS组合枚举的本质这些变形题都可以迅速套用。CSP-J的T2、T3经常在这种模型上做文章所以花一个晚上彻底搞懂P1036是性价比极高的投资。7.2 组合类型题目的通用模板这里总结一个通用DFS组合模板大家可以抄下来反复用void dfs(int start, int cnt, ...) { if (达到选择数量) { 处理结果; return; } for (int i start; i n - (还需要选几个) 1; i) { 选择a[i]; dfs(i 1, cnt 1, ...); 撤销选择(如果有的话); } }这个模板适用于所有“从n个元素中选k个满足某条件”的问题。关键就是那个start参数从i 1开始保证组合的单调性。而“还需要选几个”通常就是k - cnt。这个1的边界错误我在前面踩过请务必记住。这个模板比排列模板更常用因为竞赛中组合问题的比例远高于排列问题而很多选手恰恰在组合问题里栽跟头。7.3 一道好题对新手成长的三重意义用P1036作为训练题我认为至少有三个方面的新手红利。第一是“代码量红利”不到40行的代码包含递归、回溯或值传递回溯、剪枝、素数判断覆盖了入门阶段最重要的语法和算法知识点。第二是“调试红利”题目规模小非常适合用console逐行打印递归过程训练读递归和定位bug的能力。第三是“思维红利”从全排列到组合的思维转变是很多选手算法水平的分水岭尽早跨越这道坎后续学习状态压缩、记忆化搜索会更加轻松。我还记得当年带社团的时候有个学生第一天连DFS是什么都不知道三天后能把这道题讲得头头是道甚至能指出我代码里存在的边界隐患。这道题承载的不仅仅是算法更是一种“把一个复杂问题拆成搜索框架判断函数”的解决思路。这种思路一旦建立后续所有搜索题都会变得有章法。8. 个人实操经验与避坑清单最后分享一些我实际刷题和带新人过程中总结出的经验。这些细节不一定写进教科书但对真正做题很有帮助。第一先用手算验证样例再写代码。我见过太多人拿到题就开敲写完发现样例都过不了回头debug半天才发现是题目理解错了。手算样例的过程其实就是在头脑里跑一遍算法是最快发现思路漏洞的方式。第二巧用输出调试。在DFS入口打印start、cnt、sum三个参数在出口打印每个组合和判断结果能直观看到搜索流程是否符合预期。遇到样例通过但提交WA时构造几个小规模特殊数据比如n1、k1或者全为负数、全为0的情况往往一两组极限数据就能定位问题。第三关于取模优化请勿过早追求。很多人一看到复杂度分析就开始想各种优化但在算法竞赛里“能过就是王道”P1036这种规模的题最简单的写法就是最好的写法。花一个小时优化到0.1秒不如把这一个小时用来多刷两道同类题。第四如果是在洛谷上刷题建议开启“独立写代码”模式不要一上来就看题解。这道题网上题解很多但真正自己从设计参数、写循环、调bug走过来学到的东西要比看十篇题解都多。我记得当年自己第一次AC这道题的时间大约是在学习DFS后的第二周那种从“看不懂递归”到“能自己写出来”的成就感是支撑我继续刷题的重要动力。第五这道题还有一个进阶玩法把k扩展到任意值或者把“和为素数”换成“和为完全平方数”你只需要改一行判断代码就能变成一道新题。用这种方式做变式训练比机械刷量更有效。我自己在带集训队时经常用这道题布置“加餐作业”——让队员自己设计变体然后互相出题、互相评测效果非常好。P1036这个题号对老选手来说是一种情怀对新选手来说是一块跳板。它不高深不炫技却承载着几乎所有搜索题共通的思维方式。如果你正在备赛一定不要因为它是2002年的老题就轻视它把这道题吃透你收获的不仅仅是一个AC记录更是一整套组合搜索的心法。