企业官网建设流程全解析

1. 选数问题在考什么：拆开包装看本质

接触过 NOIP 普及组的选手，基本都绕不开 P1036 这道题。题目描述很短：给 n 个正整数，从里面任选 k 个，把选出来的数加起来，判断这个和是不是素数，最后输出和为素数的方案总数。代码量不到四十行，但当年考场上在这道题上翻车的人真不少。

4 3 3 7 12 19

这组样例对应四种选法：3+7+12=22，3+7+19=29，3+12+19=34，7+12+19=38，其中只有 29 是素数，所以答案是 1。

表面看这题只考"枚举组合 + 素数判断"两个点。但往深了说，它真正在考三件事：能不能把"任选 k 个"翻译成可执行的搜索过程；会不会在搜索时通过参数控制顺序，避免同一组数被重复计数；对素数判断的理解是不是还停留在"从 2 试到 x-1"的原始阶段。

1.1 数据范围直接决定你的写法

题目里 n 的上限一般是 20，k 不超过 n，xi 最大能到 5000000。这意味着组合数的规模在 C(20, k) 这个量级，最坏情况发生在 k=10 时，大约是 18 万多种组合。这个规模下，暴力枚举所有组合是完全可行的，不需要什么高级剪枝，也不需要记忆化搜索。

但同样的数据范围放在别的场景里可能就会出事：如果你用全排列去枚举，那就是 P(20, 10)，约 6.7 万亿种，直接跑死。所以这道题虽然代码简单，但"枚举组合"和"枚举排列"的差异，恰恰是第一道分水岭。

1.2 组合与排列的本质区别

组合不关心顺序，{3, 7, 19} 和 {7, 3, 19} 是同一种选法。如果你写三层循环去枚举，只要保证每层起点比上一层大，就能天然避免重复。换成递归写法，这个"起点递增"的约束就落在 DFS 的start参数上。

理解了这个，你才明白为什么很多人写的 DFS 里有一个start，而不是每次都从 0 开始。从 0 开始是排列的逻辑，从start开始才是组合的逻辑。这个细节不搞清楚，代码跑出来的答案铁定偏大，而且你自己还看不出来问题在哪。

2. DFS 生成组合：一个 start 参数省掉所有重复

组合问题最经典的做法就是 DFS 回溯。核心思路是：每次递归决定"下一个选谁"，同时用一个参数记录"我该从哪个位置开始选"，保证后面的选择范围永远在当前下标之后。

2.1 标准写法与逐行解读

int n, k, ans; int a[25]; void dfs(int step, int start, int sum) { if (step == k) { if (isPrime(sum)) ans++; return; } for (int i = start; i < n; i++) { dfs(step + 1, i + 1, sum + a[i]); } }

step记录已经选了几个数，start表示这一层可以从哪个下标开始尝试，sum是当前已选数的累加和。递归终止条件是step == k，说明已经选满 k 个数，这时候只需要判断sum是不是素数。

关键在dfs(step + 1, i + 1, sum + a[i])这个递归调用：第二层的起点被强制设为i + 1，这就砍掉了所有"往回选"的可能。比如第一层选了下标 2 的数，第二层就只能从下标 3 开始，永远不会再碰下标 0 到 2。整个搜索过程生成的序列下标是严格递增的，对应到数学上就是标准的组合枚举。

这种写法的好处是状态里不需要额外开布尔数组记录哪些数用过。排列问题要vis[]是因为每个位置都可能选到任何一个未用过的数，而组合问题用起点递增就堵死了重复路径，省内存也省判断。

2.2 另一种思路：每个数选或不选

除了上面这种"选下一个"的写法，还有一种常见的递归分支方式——对每个数做"要"或"不要"的决定：

void dfs(int idx, int cnt, int sum) { if (cnt == k) { if (isPrime(sum)) ans++; return; } if (idx == n) return; // 选当前这个数 dfs(idx + 1, cnt + 1, sum + a[idx]); // 不选当前这个数 dfs(idx + 1, cnt, sum); }

这种写法的本质是二叉树遍历，每个节点分两支，深度为 n，但因为有cnt == k提前收口，实际展开的节点数比 2^n 小得多。两种写法最终生成的组合集合完全一样，区别只在于思考角度：第一种是"从剩下的数里挑下一个"，第二种是"逐个决定每个数的去留"。

我个人的习惯是推荐第一种，因为step + start + sum三个参数对应"选了几个、能选谁、和是多少"，信息更直观，调试的时候打日志也方便看状态变化。第二种适合在需要额外剪枝的场景下用，比如已经选够 k 个数但还有剩余元素时，可以在cnt == k处直接返回，不用再继续往后走。

3. 素数判定：试除法的正确打开方式

选好组合之后，剩下的工作就是判断 sum 是不是素数。素数在数学上的定义是不大于 1 的自然数中，除了 1 和它本身以外不再有其他因数。注意，1 不是素数，2 是最小的素数，这两个边界条件在代码里特别容易漏。

3.1 为什么只要试到平方根

判断一个数 x 是否为素数，最朴素的办法是从 2 试到 x-1，看有没有能整除的因子。但仔细想一下：如果 x 有一个大于 sqrt(x) 的因子 d，那么 x/d 一定是小于 sqrt(x) 的因子。也就是说，因子是成对出现的，一大一小。只要小的那边没有因子，大的那边也必然没有。

所以循环只需要跑到i * i <= x就够了。sum 的最大值不会超过 k 乘 xi 的上限，按 n=20、xi=5000000 算，sum 最大约一亿，sqrt(1e8) 才一万。也就是说每组组合最多试除一万次，18 万组组合就是 18 亿次模运算。听着吓人，但实际数据基本到不了这个极端，而且很多数在试除到 3 或 5 的时候就提前 break 了，真实耗时远低于理论最坏值。

3.2 一个隐藏的溢出风险

判断条件写成i * i <= x的时候，要注意 i 和 x 的类型。如果 x 是 int，i 最大到 sqrt(INT_MAX) 也就是 46340 左右，i 乘 i 还在 int 范围内。但如果你把 x 的范围放大到十亿级以上，i 的平方就可能溢出 int，导致判断条件变成死循环或者提前退出。

这道题的数据范围里 sum 用 int 存是够的，但谁也不能保证以后做题不会遇到更大的数据。稳妥的做法是把相关变量都声明成long long，或者用i <= x / i这种不乘法的写法：

bool isPrime(long long x) { if (x < 2) return false; for (long long i = 2; i <= x / i; i++) { if (x % i == 0) return false; } return true; }

i <= x / i和i * i <= x在数学上等价，但完全避开了乘法溢出的问题。这算是一个很小的细节，可是在正式比赛里，这种细节往往就是 AC 和 WA 的分界线。

3.3 需不需要上米勒-拉宾

有读者可能会问，既然要判这么多组和，用 Miller-Rabin 或者预处理素数表会不会更快？答案是：这道题不需要。

试除法在数据范围内已经足够通过，而且 Miller-Rabin 的常数并不小，对一亿以内的数来说优势不明显。预处理素数表倒是可以考虑：先筛出 sqrt(最大和) 以内的所有素数，然后用这些素数去试除 sum，试除次数从一万次降到一千多次。不过在 n=20 的规模下，这点提升远不如把 DFS 写对来得重要。

4. 完整参考代码与复杂度账本

把前面的 DFS 和素数判断拼起来，就是这道题的完整解法。我下面给出完整的 C++ 实现，这段代码可以直接提交到 OJ 上。

4.1 完整实现

#include <bits/stdc++.h> using namespace std; int n, k, ans; int a[25]; bool isPrime(int x) { if (x < 2) return false; for (int i = 2; i * i <= x; i++) { if (x % i == 0) return false; } return true; } void dfs(int step, int start, int sum) { if (step == k) { if (isPrime(sum)) ans++; return; } for (int i = start; i < n; i++) { dfs(step + 1, i + 1, sum + a[i]); } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> k; for (int i = 0; i < n; i++) { cin >> a[i]; } dfs(0, 0, 0); cout << ans << '\n'; return 0; }

ios::sync_with_stdio(false)和cin.tie(nullptr)这两行是输入输出加速，刷题习惯了都会加上，在数据量大的时候能明显减少 IO 耗时。注意答案变量 ans 要声明成全局变量或者用引用传递，不然递归层数一变就容易丢值。

4.2 复杂度账本怎么算

时间复杂度分两部分：组合生成和素数判断。

组合生成部分，DFS 展开的节点数等于所有满足step <= k的中间状态数，加起来大约是 C(n, 0) + C(n, 1) + ... + C(n, k) 的量级。当 k=10、n=20 时，大约是 61 万个节点，完全可接受。每个叶子节点调用一次素数判断，每次判断最多试除 sqrt(sum) 次，所以总复杂度是 O(C(n, k) * sqrt(k * max(xi)))。

空间复杂度很简单：递归深度最多 k 层，加上一个长度为 n 的数组，总空间就是 O(n + k)，几乎是零额外开销。

4.3 可选的优化手段

如果你对性能有执念，可以试试这几个方向的优化：

• 在dfs开头加一个剪枝：如果剩下可选的数量n - start已经不足k - step，直接返回，因为无论如何都凑不满 k 个数了。
• 素数判断时先查一个小素数表（比如 2、3、5），能被整除就直接返回 false，能省掉不少大循环。
• 如果测试数据有多组，可以把已经判断过的 sum 存进哈希表，重复的 sum 直接复用结果。不过这道题通常只有一组数据，这个优化用不上。

5. 我在调试这道题时踩过的三个坑

这道题代码虽然短，但越是短的代码越容易在细节上栽跟头。我把自己实际踩过的坑和帮别人调试时见过的典型错误整理出来，每一个都对应具体的错误现象和原因。

5.1 递归参数传错：start 和 i+1 的区别

我第一次写这道题的时候，递归调用写成了dfs(step + 1, start + 1, sum + a[i])，结果答案比标准答案多了不少。原因在于start + 1和i + 1根本不是一回事。下一层的可选取范围应该从当前真正选中的下标i之后开始，而不是从上一层的起始位置往后挪一位。

举个例子就明白了：n=5 时，第一层start=0的循环里i会依次取 0、1、2、3、4。如果第二层传的是start + 1，那无论第一层选了哪个 i，第二层都只能从下标 1 开始。当第一层选了 i=2 时，第二层还能选下标 1 的数，这就产生了下标非递增的组合，和第一层选了 i=1 再选下标 2 的组合完全重复。

排查这类问题有个笨办法：在dfs入口把step, start, i, sum全部打印出来，跟着跑几轮，很快就能发现递归参数传递的异常。

5.2 素数的边界：1 和 0 的处理

组合出来的和最小可能是三个最小的正整数相加，直接等于 3 甚至 2，一般不会出现 1 或 0 的情况。但如果 k=1，且输入数据里有 x=1，那 sum 就可能等于 1。

判断函数里必须有if (x < 2) return false;这一行，否则 1 会被误判成素数。很多新手只在循环里判断x % i == 0，忘了处理小于 2 的情况，遇到特殊数据就会崩。这种数据往往不在样例里，只有提交之后 WA 了你才会发现。

5.3 数组越界和读取顺序

还有一个容易忽略的问题是输入顺序。题目是先给 n 和 k，再给 n 个数，但我在帮人调试时见过有人把读取顺序写反了，导致k被读成一个大数，DFS 直接跑飞。虽然不是算法问题，但考场上一紧张就容易写错。建议养成分行读取的习惯：

cin >> n >> k; for (int i = 0; i < n; i++) cin >> a[i];

还有一点，a 数组的容量要留够。n 最大 20，声明成a[25]没问题，但如果你习惯用a[20]，一旦循环写成i <= n就会出现下标越界。这种越界在本地不一定会报错，但在 OJ 上有时会表现为莫名其妙的运行时错误。

6. 这道题能迁移到哪些地方

P1036 虽然是一道普及组的老题，但它的解法骨架在后续很多题目里都能见到。组合生成的 DFS 模式、参数状态设计、剪枝思路，这些东西的价值远不止这一道题。

6.1 同一套模板能解的变式

• 求组合的具体方案：在 DFS 里多开一个path[]数组，选中的数记下来，到step == k时输出。
• 组合总和问题：比如 LeetCode 40 这类题，在step == k或者sum == target时记录答案，区别只是终止条件不同。
• 有重复元素的组合去重：先把数组排序，DFS 循环里如果i > start && a[i] == a[i-1]就跳过，避免同一层选择相同的数。
• 数的划分类问题：把"选 k 个数"改成"把 n 分成 k 个正整数"，同样用这个带起点递增的 DFS 框架。

6.2 从普及组到提高组的衔接

再往后学，你会发现这个 DFS 框架在动态规划、状态压缩、折半搜索里都有影子。比如 n 扩大到 40 时，C(40, 20) 太大了，暴力枚举会超时，这时候就要用 meet-in-the-middle：前一半和后一半分别枚举所有组合，再排序后双指针找满足条件的配对。这个技巧的核心思想，其实还是建立在"会枚举组合"的基础上。

还有一类问题是背包计数：给你 n 个物品，选任意个，问有多少种方式让总重量等于目标值。这类题如果 n 小，完全可以套用这道题的选/不选 DFS 写法，只是把终止条件从cnt == k改成sum == target。

6.3 学这道题真正该带走什么

我在帮学生准备比赛的时候，经常拿这道题当"组合枚举"的第一课。它不像图论、数论那些模块那样需要大量前置知识，只要会递归、知道素数的定义，就能上手。但在这么小的体量里，它浓缩了三个最重要的基本功：状态设计（step、start、sum 三个参数各司其职）、边界处理（素数判断的边界、递归终止的边界）、复杂度估算（C(n,k) 的量级判断）。

这三样东西，几乎会跟着你从普及组一路走到提高组，再到更远的比赛。所以如果你刚开始刷题，或者正在带别人入门，把这道题吃透，远比多刷十道简单模拟题更有价值。我自己现在偶尔给学生讲递归，还是会从这道题入手——因为它足够简单，简单到能让你把注意力完全放在"搜索过程本身"上，而不是被题目背景干扰。