枚举法 知识点讲解

概念

枚举法，大白话讲就是“把所有可能情况一个个试一遍”。就像你想知道 1 到 100 里有多少个质数，你就从 2 数到 100，每个数都拿个小本本记下来试一次；或者想知道哪三个不同的数加起来等于 15，你就把能想到的组合都列出来算一遍。

听起来很笨，但枚举是所有算法的基石：贪心算法本质上是“只试一个最可能的”，二分查找是“一次砍掉一半”，动态规划是“把试过的结果记下来”。只有先把枚举写对、写全，你才知道该往哪儿优化。

触发清单（看到这些信号第一时间想到本知识点） | 题干信号 | 优先考虑什么 | 对应思路 | | :--- | :--- | :--- | | 数据范围很小（n ≤ 100~1000） | 直接暴力 | 枚举所有候选 | | 题目问“有多少个”“是否存在”“输出所有解” | 穷举计数/方案 | 遍历 + 判定 | | 出现等式约束（如 a+b+c=S） | 降维枚举 | 解出第三个变量 | | 想不出高级算法但能“一个个试” | 兜底方案 | 先写朴素枚举 |

定义

枚举三问（写代码前必须回答）：

① 枚举什么？ —— 枚举哪几个变量？（一维？两维？枚举答案还是枚举方案？）
② 枚举到哪？ —— 每个变量的上下界是多少？（用约束推出最小范围，别直接开成 1e9）
③ 会不会重复？ —— 会不会把同一个方案数了两次？（顺序枚举 / 规定大小关系来去重）

复杂度心算表（先算再写，别写完才发现超时）：

经验值：一秒大约跑 1e8 次简单运算。先把上界代进去算一遍，再决定怎么写。

️ 知识用法地图（先记这张表，后面每节都会回到它）

枚举不是「无脑循环」，它的正确性来自「答案一定被遍历到」。下面推三个关键点。

推演 1 · 为什么枚举一定能对

只要满足两条就必不漏：① 答案一定落在你枚举的范围内；② 每个候选都真正检查了。所以枚举第一步是「定范围」（从哪枚举到哪），而不是急着写循环。范围定错 = 答案根本不在循环里 = 白枚举。

用法：先问「答案最大可能是多少、最小可能是多少」，把循环边界钉死。

推演 2 · 为什么剪枝不会剪掉答案

剪枝砍掉的必须是「已被证明不可能含答案」的分支——比如上界已经超过已知最优解、或按单调性后面只会更差。能剪的前提是「跳过的不含答案」。剪枝改的是「检查哪些候选」，不改「答案是否在被检查集合里」，所以不影响正确性，只减耗时。

用法：枚举超时时，先找「有没有单调性 / 上界」能让我提前 break。

推演 3 · 子集枚举 for(S=0; S<1<<n; S++) 为什么是不重不漏

S 从 0 取到 2^n - 1，每个整数的二进制恰好表示一种「第 i 位选 / 不选」的组合。遍历完所有整数 = 穷举了全部 2^n 个子集，且每个组合恰好出现一次。同理「枚举两个量」本质是在二维格点 (i,j) 上遍历，去重靠「只走 i<j」半边。

用法：遇到「n 个元素里选若干个」「所有配对」，先想 1<<n 或双层循环 + 去重。

必背：等式型枚举的降维技巧（最重要）

三变量枚举 (a, b, c) 满足 a + b + c = S —— 不要三重循环（O(n³)），而是：

//  O(n³)
for (a) for (b) for (c) if (a + b + c == S) ...

//  O(n²)：枚举 a、b，c 直接算出来
for (int a = 1; a <= S; a++)
 for (int b = 1; b <= S; b++) {
 int c = S - a - b;
 if (c >= 1 && /* c 的其他约束 */) { /* 一组解 */ }
 }

通用原则：有几个约束就能解掉几个变量。一个等式约束 → 少枚举一维。这是枚举题里最值钱的降维手法。

必背：去重的两种写法

重复计数是枚举题最常见的失分点：

// 方法一：规定大小关系（适合"组合"类，如三角形三边 a <= b <= c）
for (int a = 1; a <= n; a++)
 for (int b = a; b <= n; b++) //  b 从 a 开始，不重复
 for (int c = b; c <= n; c++) //  c 从 b 开始

// 方法二：用集合/哈希去重（适合"方案本身无序但元素集合相同"）
set<vector<int>> uniq; // 或 set<string>

判断标准：如果题目说"不考虑顺序"，就用"规定大小关系"；如果说"不同的排列算不同方案"，就不要去重。

必背：枚举 + 剪枝（把 O(n³) 砍成能过的）

剪枝 = 提前发现"再枚举下去也没用"，直接跳过。

for (int a = 1; a <= n; a++) {
 if (/* a 已经不满足必要条件 */) continue; // ① 单层剪枝
 for (int b = a; b <= n; b++) {
 if (a + b > S) break; // ② 用单调性 break（不是 continue！）
 // ...
 }
}

三个常用剪枝方向：

1. 上界剪枝：把循环上界从 n 缩到"理论上可能的最大值"（比如求 a*b = n 时，a 只需要枚举到 sqrt(n)）；

2. 单调性剪枝：内层变量递增时，某个条件一旦不满足，后面更大也不可能满足 → 用 break 而不是 continue；

3. 可行性剪枝：当前枚举的组合已经超出约束（和已经大于 S），直接停。

必背：枚举的四种优化路线（超时时按顺序试）

更多同类真题（来自真题库，点击展开）

例题

找三个不同的正整数，和为 9，且第一个小于第二个。（a < b < c）

int S = 9;
for (int a = 1; a <= S; a++)
 for (int b = a + 1; b <= S; b++) { //  b 从 a+1 开始 → 自动满足 a < b 且不重复
 int c = S - a - b; //  用等式解出 c，省掉一重循环
 if (c > b) printf("%d %d %d\n", a, b, c);
 }

输出：

1 2 6
1 3 5
2 3 4

这道题把枚举的三件事全体现了：① 用等式降掉一维（c = S - a - b）；② 用 b = a + 1、c > b 去重（保证 a < b < c）；③ 上界收紧（a、b 都只到 S，且实际更早就不满足了）。

️ 图示与代码示例

用"统计 1~n 中的质数个数"作为枚举法的典型例题：对每个候选数 i，再枚举它的可能因子 j（从 2 到 √i）判断能否整除，若都不能整除则 i 是质数。

按此思路写出完整可运行代码（CCF 风格，关键行加中文注释）：

#include <iostream>
#include <cmath>
using namespace std;

// 判断 x 是否为质数：从 2 枚举到 sqrt(x)，看有没有因子
bool isPrime(int x) {
 if (x < 2) return false; // 0、1 不是质数
 for (int j = 2; j * j <= x; j++) // j 只枚举到 √x 即可
 if (x % j == 0) return false; // 找到一个因子就不是质数
 return true;
}

int main() {
 int n, cnt = 0;
 cin >> n; // 读入上界 n
 for (int i = 1; i <= n; i++) // 外层枚举每一个候选数
 if (isPrime(i)) cnt++; // 是质数就计数 +1
 cout << cnt << endl; // 输出 1~n 中质数的个数
 return 0;
}

要点小结：枚举的两层循环——外层"枚举所有候选答案"、内层"检验每个候选是否合法"。当 n 不大时，这就是稳妥的正解；n 变大时再用"只枚举到 √x"等剪枝加速。

例题复盘总结

共性特征：

• 题目要求输出所有解或计数，数据范围较小（通常 n ≤ 1000）；
• 存在等式约束（如和为定值），可降维；
• 需要去重（组合类）或按顺序输出（排列类）。

各自技巧：

• 降维：看到 a+b+c=S 立刻想到解出第三个变量，避免三重循环。
• 去重：组合类用 a<b<c 或 b 从 a 开始；排列类用 next_permutation。
• 剪枝：内层单调递增时，一旦不满足条件直接 break 而非 continue。

审题模板（固定思考流程）：

1. 看数据范围：n 多大？能枚举几维？

2. 数约束个数：几个等式？能解掉几个变量？

3. 定枚举对象：是枚举答案（求最大/最小）还是枚举方案（输出所有）？

4. 定边界：上界能不能用约束推得更紧？

5. 定去重：题目说“不考虑顺序”还是“不同排列算不同”？

6. 写朴素版：先跑对样例，再优化。

错误清单（只列特有错误）：

• 三重循环枚举 a+b+c=S 却忘了降维，导致 O(n³) 超时。
• 组合类枚举时 b 从 1 开始，导致重复计数。
• 内层循环条件不满足时用了 continue 而非 break，白跑大量无用代码。
• 枚举范围开太大（如 a 到 1e9），实际只需到 sqrt(n)。
• 忘记排除平凡解（如 0 不是正整数）或相等元素。
• 整数溢出：枚举里的乘积（a * b）容易爆 int，应先用 long long 估算。
• 见下节（常见错误）。

写法总表

分工说明：触发清单告诉你“什么时候想到枚举”，技巧速查表告诉你“具体怎么写”，写法总表告诉你“遇到哪类问题用哪招”。

常见错误

1. 不估复杂度就写：n ≤ 1e5 写三重循环，交上去才发现 TLE —— 浪费一次提交机会。先算再写。

2. 重复计数：用 for (a) for (b) 枚举“无序对”时会算两遍。规定大小关系或用集合去重。

3. 该 break 却写 continue：内层变量递增、条件单调时，一旦不满足后面全不满足，continue 会白跑很多次（甚至超时）。

4. 上界开太大：a 枚举到 1e9 但实际最多到 sqrt(n) —— 白白多跑几万倍。

5. 忘记排除平凡解：题目说“正整数”，别忘了 0 不是正整数；说“不同”，别忘了排除相等。

6. 整数溢出：枚举里的乘积（a * b）容易爆 int。先估算最大值，拿不准用 long long。

自测

1. 一秒大约能跑多少次运算？n = 1000 的三重循环能过吗？

2. 要枚举 a + b + c = S 的所有正整数解，怎么用两重循环完成？

3. 枚举“三角形三边”时，怎么保证不重复计数？

4. 什么时候内层循环该用 break 而不是 continue？举例说明。

5. 数据范围 n ≤ 1e5 而你只能想到 O(n²) 的枚举，有哪几条优化路线？

6. 枚举题提交前，你会专门检查哪两件事？

举一反三 · 审题流水线

拿到题先别急着敲代码，按这个流水线走一遍：

1. 扫一眼数据范围：n 是多少？这直接决定能枚举几维。

2. 圈出所有约束：等式有几个？不等式有几个？每个等式能解掉一个变量吗？

3. 判断枚举对象：是求最大值/最小值（枚举答案），还是输出所有解（枚举方案）？

4. 估算复杂度：按最坏情况算算循环次数，代入 n 看会不会超时。

5. 设计去重策略：题目说“不考虑顺序”还是“排列不同算不同”？

6. 写最朴素的版本：先保证正确，再考虑剪枝和优化。

练手题

题一：给定一个正整数 n，求 1 到 n 之间所有满足“各位数字之和等于 9”的整数个数。

• 提示：枚举每个数，计算各位数字之和，判断是否等于 9。
• 数据范围：n ≤ 10000。

题二：给定一个正整数 S，求所有满足 a + b + c = S 且 a < b < c 的正整数三元组 (a, b, c) 的个数。

• 提示：枚举 a 和 b，用等式解出 c，检查是否满足 c > b。
• 数据范围：S ≤ 50。