基础算法之枚举算法教学讲义

---

一、概念定义、价值意义

1.1 什么是枚举算法

枚举算法（Enumeration / Brute Force）：将问题的所有可能解一一列举出来，逐一检验每个候选者是否满足题目条件，从而找到正确答案的算法策略。

枚举法又称穷举法，是计算机算法中最基础、最直观的方法。它不依赖巧妙的数学推导，而是利用计算机高速运算的能力，通过“全面撒网”来解决问题。

1.2 价值意义

• 思维简单：不需要复杂的算法设计，直接按照问题描述翻译成代码。
• 保证正确性：只要解空间有限且枚举完整，就不会遗漏任何解。
• 通用性强：几乎任何问题都可以用枚举法得到一个可行解（虽然可能超时）。
• 验证基准：常用于验证其他算法（如贪心、DP）的正确性，作为对拍程序。
• 竞赛实用：当数据范围很小（如 n ≤ 20，或取值范围 ≤ 10⁶）时，枚举往往是满分或部分分解法。

---

二、算法原理、算法框架、图示解析

2.1 核心思想

枚举算法的核心可以概括为四个字：列举、检验。

1. 列举：确定解空间的范围，用循环或递归生成所有候选解。
2. 检验：对每个候选解，判断其是否满足题目条件。

2.2 算法框架（伪代码）

Enumeration():
    for each candidate in solution_space:
        if check(candidate) == true:
            record or output candidate

2.3 图示解析（图框内文字用简单英文）

        Start
          │
          ▼
   ┌───────────────┐
   │ Define        │
   │ solution space│
   └───────┬───────┘
           │
           ▼
   ┌───────────────┐
   │ Generate next │◄───┐
   │ candidate     │    │
   └───────┬───────┘    │
           │            │
           ▼            │
   ┌───────────────┐    │
   │ Check if      │    │
   │ valid?        │    │
   └───────┬───────┘    │
           │            │
      ┌────┴────┐       │
     Yes       No       │
      │         │       │
      ▼         │       │
   ┌───────┐    │       │
   │Record │    │       │
   └───┬───┘    │       │
       │        │       │
       └────────┼───────┘
                │
           more candidates?
           │         │
          Yes        No
           │         │
           └─────┐   ▼
                 │  ┌───────┐
                 │  │Output │
                 │  │result │
                 │  └───────┘
                 │
           (loop back)

---

三、代码模型、代码模板

3.1 基础模板：单层循环枚举

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 定义解空间范围 [L, R]
    for (int i = L; i <= R; i++) {
        if (check(i)) {
            // 找到解
            cout << i << endl;
        }
    }
    return 0;
}

3.2 多重循环枚举（组合枚举）

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 10;  // 假设范围 1~10
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            for (int k = j + 1; k <= n; k++) {
                if (check(i, j, k)) {
                    cout << i << " " << j << " " << k << endl;
                }
            }
        }
    }
    return 0;
}

3.3 递归枚举（全排列、子集）

#include <bits/stdc++.h>
using namespace std;

vector<int> path;
bool used[10];

void dfs(int depth, int n) {
    if (depth == n) {
        // 生成一个完整候选解
        if (check(path)) {
            // 输出或记录
            for (int x : path) cout << x << " ";
            cout << endl;
        }
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            used[i] = true;
            path.push_back(i);
            dfs(depth + 1, n);
            path.pop_back();
            used[i] = false;
        }
    }
}

3.4 二进制枚举（子集）

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 5;
    vector<int> arr = {1, 2, 3, 4, 5};
    // 枚举所有非空子集
    for (int mask = 1; mask < (1 << n); mask++) {
        vector<int> subset;
        for (int i = 0; i < n; i++) {
            if (mask >> i & 1) subset.push_back(arr[i]);
        }
        // 对 subset 进行检验
    }
    return 0;
}

---

四、基本要素、基本方法、基本步骤

4.1 基本要素

要素	说明
解空间	所有可能解的集合，必须能完整无遗漏地枚举
枚举方式	循环、递归、位运算等生成候选解的方法
检验条件	判断候选解是否为有效解的逻辑表达式
记录/输出	保存满足条件的解，或统计个数、求最值等

4.2 基本方法

1. 直接循环枚举：适用于变量个数少、范围小的问题（如百钱买百鸡）。
2. 多重循环枚举：适用于组合问题（如从 n 个数中选 m 个）。
3. 递归回溯枚举：适用于排列、子集、N 皇后等问题。
4. 二进制枚举：适用于子集枚举（用 0/1 表示选或不选）。
5. STL 枚举：next_permutation 枚举全排列。

4.3 基本步骤

1. 分析解空间：确定哪些变量需要枚举，它们的取值范围。
2. 设计枚举方式：选择合适的循环结构或递归。
3. 编写检验函数：将题目条件翻译成 C++ 表达式。
4. 优化剪枝（可选）：提前排除明显不可能的候选，减少枚举量。
5. 输出结果：按题目要求输出（计数、打印、求最值等）。

---

五、经典例题（3题，含思路解析和详细注释）

例题1：百钱买百鸡（经典枚举优化）

题目描述

公鸡 5 元一只，母鸡 3 元一只，小鸡 1 元三只。用 100 元买 100 只鸡，问公鸡、母鸡、小鸡各多少只？输出所有可能的组合，每行一组。

思路解析

• 设公鸡 x 只，母鸡 y 只，小鸡 z 只。
• 约束：x + y + z = 100，5x + 3y + z/3 = 100，且 z 能被 3 整除。
• 直接三重循环：x:0~100，y:0~100，z:0~100，复杂度 101³ ≈ 10⁶，可接受。
• 优化：利用 x+y+z=100 消去 z，只需枚举 x 和 y，z = 100-x-y，再判断整除和价格。x 最多 20（520=100），y 最多 33（333=99），复杂度约 20*33=660。

代码实现（优化版）

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 公鸡最多 20 只，母鸡最多 33 只
    for (int x = 0; x <= 20; x++) {
        for (int y = 0; y <= 33; y++) {
            int z = 100 - x - y;
            if (z % 3 == 0 && 5 * x + 3 * y + z / 3 == 100) {
                cout << x << " " << y << " " << z << endl;
            }
        }
    }
    return 0;
}

例题2：火柴棒等式

题目描述

给定 n 根火柴棒（n ≤ 24），拼出形如 A + B = C 的等式。数字 0~9 的火柴棒根数分别为 {6,2,5,5,4,5,6,3,7,6}。加号和等号各用 2 根。A、B、C 均为非负整数，且若数字不为 0 则最高位不能是 0。求能拼出的等式总数（A≠B 时交换算两个）。

思路解析

• 先确定枚举范围：n 最大 24，去掉加号和等号 4 根，剩余最多 20 根。数字 1 只用 2 根，所以最大数字不会太大（1111 约需 8 根）。经验范围 0~1111 足够。
• 预处理函数 cnt(x) 计算数字 x 所需火柴根数。
• 枚举 A 和 B，计算 C = A + B，检查 cnt(A)+cnt(B)+cnt(C) == n-4。
• 注意：当 AB 且 A!=0 时，同一组等式只算一次？题目说如果 A!=B，则交换算两个；AB 时只算一个。实际上在枚举中，当 A==B 时，只会被枚举一次，所以不需要额外处理。但需注意 0+0=0 这种情况，火柴数 6+6+6+4=22，若 n=22 会被计入一次。

代码实现

#include <bits/stdc++.h>
using namespace std;

int cost[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};

// 计算数字 x 需要多少根火柴
int getCost(int x) {
    if (x == 0) return cost[0];
    int res = 0;
    while (x > 0) {
        res += cost[x % 10];
        x /= 10;
    }
    return res;
}

int main() {
    int n;
    cin >> n;
    int total = 0;
    int limit = 1111;  // 经验上限
    for (int a = 0; a <= limit; a++) {
        for (int b = 0; b <= limit; b++) {
            int c = a + b;
            if (getCost(a) + getCost(b) + getCost(c) == n - 4) {
                total++;
            }
        }
    }
    cout << total << endl;
    return 0;
}

例题3：有效三角形个数（枚举所有三元组）

题目描述

给定一个包含非负整数的数组 nums，统计其中可以组成三角形三条边的三元组个数。例如，输入 nums = [2,2,3,4]，输出应为 3（[2,3,4] 使用第一个2、[2,3,4] 使用第二个2、[2,2,3]）。

思路解析

• 三重循环枚举所有三元组 (i, j, k) 且 i < j < k。
• 检验条件：任意两边之和大于第三边。由于三个数排序后只需检查最小两边之和大于最大边，但此处直接检验三个条件即可。
• 时间复杂度 O(n³)，当 n ≤ 100 时可接受。

代码实现

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];
    
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                int a = nums[i], b = nums[j], c = nums[k];
                if (a + b > c && a + c > b && b + c > a) {
                    count++;
                }
            }
        }
    }
    cout << count << endl;
    return 0;
}

---

六、课后练习（20题，含可直接点击的链接）

以下题目涵盖各种枚举技巧，难度递进，建议按顺序完成。

力扣（LeetCode）

序号	题目名称	题号	链接
1	两数之和	1	https://leetcode.cn/problems/two-sum/
2	三数之和	15	https://leetcode.cn/problems/3sum/
3	四数之和	18	https://leetcode.cn/problems/4sum/
4	子集	78	https://leetcode.cn/problems/subsets/
5	全排列	46	https://leetcode.cn/problems/permutations/

信息学奥赛一本通（ybt.ssoier.cn）

序号	题目名称	题号	链接
6	百钱买百鸡	1022	https://ybt.ssoier.cn/problem_show.php?pid=1022
7	统计平方和	1023	https://ybt.ssoier.cn/problem_show.php?pid=1023
8	因子分解	1200	https://ybt.ssoier.cn/problem_show.php?pid=1200
9	子集和问题	1291	https://ybt.ssoier.cn/problem_show.php?pid=1291
10	排列	1199	https://ybt.ssoier.cn/problem_show.php?pid=1199

洛谷（Luogu）

序号	题目名称	题号	链接
11	三连击	P1008	https://www.luogu.com.cn/problem/P1008
12	全排列问题	P1706	https://www.luogu.com.cn/problem/P1706
13	组合的输出	P1157	https://www.luogu.com.cn/problem/P1157
14	火柴棒等式	P1149	https://www.luogu.com.cn/problem/P1149
15	回文质数	P1217	https://www.luogu.com.cn/problem/P1217

Codeforces

序号	题目名称	题号	链接
16	1360A - Minimal Square	1360A	https://codeforces.com/problemset/problem/1360/A
17	1579B - Shifting Sort	1579B	https://codeforces.com/problemset/problem/1579/B

AtCoder

序号	题目名称	题号	链接
18	ABC 085 B - Kagami Mochi	ABC085B	https://atcoder.jp/contests/abc085/tasks/abc085_b
19	ABC 122 B - ATCoder	ABC122B	https://atcoder.jp/contests/abc122/tasks/abc122_b

AcWing

序号	题目名称	题号	链接
20	数的范围	789	https://www.acwing.com/problem/content/791/

---

七、注意事项

1. 解空间大小：枚举前务必估算时间复杂度，确保在题目时限内可运行。通常 1 秒内可执行约 10⁷~10⁸ 次简单操作。
2. 循环变量范围：尽量通过数学分析缩小枚举范围（如百鸡问题中公鸡≤20）。
3. 避免重复枚举：组合问题中，用 j=i+1 等方式避免 (i,j) 和 (j,i) 重复。
4. 浮点数精度：避免直接比较浮点数相等，可用整数运算代替（如小鸡价格用 z%3==0 和整数运算）。
5. 剪枝优化：在循环内提前判断不可能的情况，用 continue 或 break 跳过。
6. 递归枚举注意栈溢出：深度较大时改用非递归或 BFS。
7. 使用 STL 加速：next_permutation 枚举全排列非常方便。
8. 考虑边界条件：如空数组、单个元素、最大值最小值等。

---

八、课堂总结

核心要点	说明
枚举算法定义	列举所有可能解，逐一检验。
适用场景	解空间较小（如 n≤20，取值范围可枚举）的问题。
时间复杂度	通常 O(N^k)，N 为单个变量取值范围，k 为变量个数。
优点	简单、可靠、不易出错，可作为验证基准。
缺点	效率低，不适用于大规模数据。
优化方向	缩小枚举范围、剪枝、降维（减少循环层数）。
与搜索算法关系	深度/广度优先搜索本质也是枚举，但利用了状态空间剪枝。

教练寄语：枚举算法是信息学竞赛的“基本功”，看似笨拙，却是通向更高级算法的必经之路。当你遇到一道题毫无思路时，不要忘记枚举——也许它就能为你赢得部分分甚至满分。更重要的是，通过枚举你能深入理解问题的解空间结构，为后续学习搜索、动态规划打下坚实基础。

---

参考资料

• 【书籍】《啊哈！算法》第1章：排序与枚举
• 【书籍】《信息学奥赛一本通》第5章：搜索与回溯
• 【在线资源】OI Wiki - 枚举
• 【在线资源】洛谷 - 枚举题单