Lecture 6: 递归回溯与枚举（Recursive Backtracking & Enumeration）（对应课程真实讲座 L11–L12）

目录 · ← l5 · l7 →

Lecture 6: 递归回溯与枚举（Recursive Backtracking & Enumeration）（对应课程真实讲座 L11–L12）

概述

本讲在”枚举”（序列、排列、子集）的基础上引入递归回溯（recursive backtracking）：沿着决策点一步步尝试，撞上死胡同就退回上一个决策点换一条路，并把这一范式归纳为三字诀 choose–explore–unchoose（选择—探索—撤销）。我们会用生成子集、集合平分 isPartitionable、0-1 背包三个经典问题吃透回溯骨架与指数复杂度，为后面迷宫、数独等”迭代很难写”的问题储备通用武器。 （对应官方 2026 夏季 CS106B：L11 Thursday, July 9 “Recursive Backtracking and Enumeration”；L12 Monday, July 13 “More Recursive Backtracking”。官方用迷宫小人动画演示回溯：一路 Search…，碰壁就 Backtrack… 回到上一个岔路口换方向。）

核心概念与算法原理

1. 序列、排列、子集：三类枚举问题一家亲 官方在第 11 讲先做了小结：我们已能用递归生成三类结果——序列（抛 n 次硬币 2ⁿ 种、掷 n 次骰子 6ⁿ 种）、排列（”cat” 的 6 种重排）、子集（{a, c, t} 的 8 个子集，含空集）。它们都长在同一棵”决策树”上，区别只是每层的分支数（2、n、6…）与何时停止。子集问题里顺序无关，{b, a} 与 {a, b} 算同一个子集，所以决策树只需考虑”每个元素要 or 不要”，共 2ⁿ 个叶子。

2. 回溯是什么：碰壁就回头

• 问题定义：在多个连续决策构成的状态空间中搜索满足条件的解；当前路径走到头仍无解（死胡同 dead end）时，回到最近一个还有未试选项的决策点，改走另一条路，而不是从头重来。
• 直观解释：走迷宫——每个岔路口是一个决策点；走到死路就退回上一个岔路口选另一条走廊；再死路再退。官方动画里的小人正是这样”Searching… / Backtracking…”反复进退。若迷宫可绕圈，还需”撒面包屑”标记走过的地方，防止在两个格子间无限往返（即回溯骨架中的”查重状态”环节）。

3. 回溯的标准骨架：choose–explore–unchoose 把回溯算法解剖开，官方在第 11 讲给出如下通用结构（每步是否必需因问题而异）：

1. 基准情形（base case）：到达叶子。若当前状态是解 → 打印/计数/返回 true；
   否则返回"此路不通"的哨兵值（false / 0）。
2.（可选）查重：若进入过相同状态（如迷宫已撒过面包屑的格子）→ 直接返回。
3. 生成候选：用循环枚举本决策点的全部合法选择；非法选择跳过（剪枝）。
   对每个候选：
   a. 改变状态（choose）     —— 把选择付诸实施（放入容器/移动棋子/计入和）
   b. 递归深入（explore）    —— 带着新状态调用自己
   c. 处理返回值（可选）     —— 命中即停（return true）或累加计数
   d. 撤销状态（unchoose）   —— 把 a 的改动还原，供下一个候选使用

关键认识：什么情况下必须显式撤销？ 官方特别指出：若问题状态（容器/网格/字符串）是按值拷贝传下去的，父调用的拷贝从未被改动，函数返回即天然回到旧状态，”撤销”就自动完成了（上一讲的子集字符串版正是如此）；若状态是按引用共享的（vector、数组、网格），子调用对它的修改会永久残留，返回后必须手动撤销，否则兄弟分支看到的是一副被掏空/改坏的状态。本节三个例子里，子集用”按值”免撤销，平分与背包用”共享容器 + 显式撤销”。

4. 子集决策树与回溯撤销示意图

上半：子集 {a, b} 的决策树（每层决定“要/不要”一个元素；叶子 = 一个子集）
                       (soFar="", 待决策 a, b)
                    /                            \
           不要 a                               要 a
           /      \                            /      \
      不要 b      要 b                     不要 b     要 b
         |          |                        |          |
        {}         {b}                      {a}       {a,b}
     (计1)       (计1)                    (计1)      (计1)
    → 叶子共 4 = 2²：每个元素两种选择，路径即子集

下半：共享容器的 choose / unchoose 必须配对（isPartitionable 的 rest 容器，示例见后）
   深入（choose + explore）                        返回（unchoose）
   rest = {1,1,2,3,5}  取出 5 → 尝试放进某一组     把 5 放回 → rest 复原
   rest = {1,1,2,3}    取出 3 → …                 放回 3 → …
   rest = {1,1,2}      取出 2 → …                 放回 2 → …
        ……                                            如果不放回，回溯到兄弟分支时
                                                     rest 已被掏空，无物可选，
                                                     结果必错（见陷阱 1）

5. 把”打印”改成”计数/返回 bool”：三种返回风格 同一副骨架，只要改基准情形的返回值与返回语句的汇总方式，就能切换用途（官方在第 11 讲把 printSubsets 改成返回子集个数，并强调这种变形必须掌握）：叶子处 return 1（或解的值）、内部用 + 汇总 → 计数；叶子处 return 布尔条件、内部用 || 汇总 → 判断”是否存在解”。bool 版本还白得一个福利——短路求值（short-circuiting）：a \|\| b 中 a 为 true 时 C++ 根本不会执行 b，于是”找到一个解就整棵树提前停止”不用写任何额外代码（官方第 11 讲用 isPartitionable 的两个版本对比了短路带来的巨大差异）。bool 函数收尾也建议直接 return sum1 == sum2; 而不是 if-else 绕弯。

6. isPartitionable：集合能否平分成两组

• 问题定义：能否把向量 V 的元素全部、恰好一次地分进两组 V₁、V₂，使两组元素和相等？例：{1,1,2,3,5} 可分（{1,5} 与 {1,2,3} 各为 6）；{1,4,5,6} 不可分。
• 思路：对每个元素做二选一（进组 1 / 进组 2），全部放完时检查两桶和是否相等。这是”子集”骨架的 bool 版本，且官方实现用了”从剩余容器取一个元素 + 递归后放回”的显式撤销写法。

7. 0-1 背包：struct 承载物品 + 剪枝

• 问题定义（官方第 12 讲）：背包容量 c，物品 i 有重量 wᵢ 与价值 vᵢ，每个物品只能整件拿或不拿（”0-1”即二选一），求不超过容量前提下的最大总价值。贪心（先拿最贵的，或按 v/w 比值拿）都不保证最优——官方给了反例：容量 10，物品 (w=8,v=160) 与三个 (3,58) 加一个 (1,2)：按比值贪心拿 8 号只能再拿 1 号得 162，而拿后四个共重 10 得 176。
• 剪枝（pruning）：某物品比剩余容量还重时，它不可能被拿，只能走”不拿”单分支——这比盲目二分少了半棵子树。官方原话是：背包问题里并非每个物品都面对二选一，”拿不动就被迫放弃”。
• C++ 配套知识——struct（结构体）：把重量与价值打包成一个新类型，避免两个平行 vector 错位（官方第 12 讲演示了 weights/values 分开存的风险）。定义写在函数外、右花括号后必须有分号；成员用 . 访问：Item i; i.weight = 4;。

8. 官方三种背包递归写法对照：为什么有的要撤销、有的不用？ 官方在第 12 讲一口气展示了三种等价写法，目的是让人看到”同题多解、各有权衡”，并强调考试不要求复刻某种写法、只要求正确可读。三者的本质差别是状态如何管理，而”要不要 unchoose”完全由此决定：

本节示例 3 采用”方案 2 + 剪枝”：既保有按引用传容器、避免按值拷贝整表的效率，又因为只用下标游走而完全免去 unchoose 簿记——是初学者最容易写对的一种。

代码示例与实现详解

下面 3 个示例只依赖 C++17 标准库，可独立编译运行。

示例 1：生成子集（打印版 + 计数版 + bool 判断版）

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// 打印版：soFar=已选元素组成的子集，rest=尚未决策的元素
void printSubsets(const string& soFar, const string& rest) {
    if (rest.empty()) {                     // 全部元素决策完毕 → 打印一个子集
        cout << "{" << soFar << "}" << endl;
        return;
    }
    string newRest = rest.substr(1);        // 剥出当前元素 rest[0] 后的剩余
    printSubsets(soFar, newRest);           // 不要 rest[0]（exclude）
    printSubsets(soFar + rest[0], newRest); // 要 rest[0]（include）
}

// 计数版：把打印换成“每片叶子贡献 1”，内部用 + 汇总
int countSubsets(const string& soFar, const string& rest) {
    if (rest.empty()) {
        return 1;                           // 到达一个完整子集 → 计 1
    }
    string newRest = rest.substr(1);
    return countSubsets(soFar, newRest) +   // 不要
           countSubsets(soFar + rest[0], newRest);   // 要
}

// bool 版：是否存在某个子集，其元素和恰好等于 target？
// nums 只读，用下标 k 游走（无需撤销）；叶子直接给出“这条路成不成”
bool hasSubsetSum(const vector<int>& nums, int k, int sumSoFar, int target) {
    if (k == (int)nums.size()) {
        return sumSoFar == target;
    }
    // 不选 nums[k] 或 选 nums[k]；|| 短路 → 一旦找到 true 立即整树停止
    return hasSubsetSum(nums, k + 1, sumSoFar, target) ||
           hasSubsetSum(nums, k + 1, sumSoFar + nums[k], target);
}

int main() {
    printSubsets("", "ab");                 // 输出 {} {b} {a} {a,b}（顺序因先 exclude）
    cout << "子集总数: " << countSubsets("", "abc") << endl;   // 8 = 2³
    cout << "存在和为6的子集: " << hasSubsetSum({1, 2, 3, 7}, 0, 0, 6) << endl; // 1（1+2+3）
    return 0;
}

【代码做什么】：printSubsets("", "ab") 沿决策树下行：每个元素先试”不要”再试”要”，到叶子（rest 空）打印 soFar，共 4 行；countSubsets 结构完全相同，仅把叶子行为从打印改成 return 1、把两条递归路径用 + 相连，于是根调用返回 2³ = 8；hasSubsetSum 是第三个”bool 风格”函数：对 nums 里每个元素同样做”不选/选”的二选一，叶子用 sumSoFar == target 判定成败，主函数里 {1,2,3,7} 存在子集 {1,2,3} 和为 6，输出 1。

【实现机制解说】：soFar/rest 都是按值参数，每层调用拿到的是父状态的拷贝，因此不需要任何显式撤销——这就是第 3 节”按值天然撤销”的实例。三个函数演示了”打印 → 计数 → 判断”的返回风格切换：叶子处 return 1 并用 + 汇总得计数；叶子处返回布尔条件并用 \|\| 汇总得判断，而 \|\| 的短路让”找到解就整棵停止”零成本发生（官方在第 11 讲强调这种变形必须熟练掌握）。代价也要看清：递归调用数 2ⁿ 是指数级，若 n 大到 30+，即使每层 O(1) 也无法承受——官方提醒，对指数算法连”每层多一次 O(n) 的字符串拷贝”都会被放大成明显变慢，面试时往往要改成传引用 + 下标的高效版。

示例 2：isPartitionable——回溯 + 显式撤销 + 短路早停

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

// rest: 还没分配的元素（共享容器，按引用）；sum1/sum2: 两组当前总和
bool isPartitionable(vector<int>& rest, int sum1, int sum2) {
    if (rest.empty()) {                 // 基准：元素全部分完 → 两桶和相等即成功
        return sum1 == sum2;
    }
    int item = rest.back();             // 从末尾取（O(1)，比从 0 号取快）
    rest.pop_back();                    // ← choose：item 离开“待分配”容器
    // explore：两条路——给组1 或 给组2。|| 短路 → 组1 成功就不再探索组2
    bool ok = isPartitionable(rest, sum1 + item, sum2) ||
              isPartitionable(rest, sum1, sum2 + item);
    rest.push_back(item);               // ← unchoose：放回，供兄弟分支继续用
    return ok;
}

// 包装函数：两组初始和都是 0
bool isPartitionable(vector<int>& v) {
    return isPartitionable(v, 0, 0);
}

int main() {
    vector<int> a = {1, 1, 2, 3, 5};
    vector<int> b = {1, 4, 5, 6};
    cout << "可分: {1,1,2,3,5} -> " << isPartitionable(a) << endl;   // 1 (true)
    cout << "可分: {1,4,5,6}   -> " << isPartitionable(b) << endl;   // 0 (false)
    return 0;
}

【代码做什么】：isPartitionable 每次从 rest 末尾取一个元素，递归尝试把它放进组 1 或组 2；rest 空了就检查两组和。主函数验证两个官方用例：{1,1,2,3,5} 可分（如 {1,5} 与 {1,2,3}），{1,4,5,6} 不可分。

【实现机制解说】：这是”共享状态 + 显式撤销”的标准样板，请对照第 3 节骨架逐行读：pop_back 是 choose；两处递归是 explore；push_back 是 unchoose，它必须与 choose 一一配对，位置在返回值算完之后、return 之前。若删掉 push_back，第一分支把 rest 掏空后不还原，回溯到上层换走另一条分支时容器是空的，函数会在半途的某个 sum 组合上误判成功——官方演示过：删掉该行后 {1,4,5,6} 会错误地返回 true。另外两处细节：短路——若组 1 的分支已返回 true，\|\| 右侧的组 2 分支根本不执行，整棵搜索树立即收工；取末尾而非取开头——pop_back/push_back 都是 O(1)，而从下标 0 移除/插入是 O(n)，在指数递归里每一层省下的 O(n) 会放大成巨大差异（官方第 11 讲的 Exam Prep 专门点了这一点）。

示例 3：0-1 背包回溯版（struct Item + 剪枝）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Item {           // 注意：struct 定义在函数外；右花括号后要有分号！
    int weight;
    int value;
};

// 从下标 k 起的物品中挑，剩余容量 capacity，返回能获得的最大价值
int knapsack(const vector<Item>& items, int capacity, int k) {
    if (k == (int)items.size()) {       // 基准：没有物品可选了
        return 0;
    }
    const Item& it = items[k];
    int best = knapsack(items, capacity, k + 1);   // 不拿：作为基线
    if (it.weight <= capacity) {        // 剪枝：拿不动只能放弃（少走半棵子树）
        int take = it.value + knapsack(items, capacity - it.weight, k + 1);
        best = max(best, take);
    }
    return best;                        // 拿与不拿中取更优
}

// 包装函数：从第 0 号物品、满容量开始
int knapsack(const vector<Item>& items, int capacity) {
    return knapsack(items, capacity, 0);
}

int main() {
    vector<Item> items1 = {{4,6}, {2,4}, {3,5}, {1,3}, {6,9}, {4,7}};  // {w, v}
    vector<Item> items2 = {{8,160}, {3,58}, {3,58}, {3,58}, {1,2}};
    cout << "容量10 最优价值: " << knapsack(items1, 10) << endl;   // 19
    cout << "容量10 最优价值: " << knapsack(items2, 10) << endl;   // 176（贪心只有162）
    return 0;
}

【代码做什么】：对每个物品做”拿/不拿”决策。拿得动才尝试拿（剪枝），拿与不拿两个候选取 max；基准是没有物品可选时价值为 0。主函数复现官方两个测试：前者最优 19（拿 2、3、5 号与 (4,7) 号：重 10 值 19），后者最优 176——顺便戳穿贪心。

【实现机制解说】：这个版本采用官方的”下标 k 推进”写法：k 表示”前 k 件已决策、从第 k 件起待决策”，因此不需要修改任何共享容器，也就没有 unchoose 环节——撤销的缺失正是按引用传递但只用下标游走的红利（官方第 12 讲的方案 2/3 都属此类，方案 1 则需要显式把取出的物品放回）。再看复杂度与剪枝：最坏情形（每件都装得下）每个节点分裂成 2，是 O(2ⁿ)；最好情形（每件都超重）只剩”不拿”单分支，退化 O(n)。官方在第 12 讲坦率指出：这套朴素回溯不是最高效解法——同一条递归树里有大量重复子问题（如”还剩容量 3、还剩物品 3..n”会反复求解），后续课程会学 memoization（记忆化）与动态规划把它优化到多项式级，本章只要求掌握回溯骨架与指数本质。

复杂度分析

说明：三个问题的共同点是”决策树叶子数随 n 指数增长”，n 每加 1 工作量翻倍——这就是官方反复强调”指数运行时不可扩展”的原因：n = 30 的 2³⁰ ≈ 10 亿次调用已接近极限，n = 60 则彻底不可行。剪枝与短路只能砍掉明显无望的分支，不能改变指数本性。

关键要点

• 把回溯背成三字诀：choose（改状态）→ explore（递归）→ unchoose（还原），三步缺一不可、顺序不乱。
• 状态按值拷贝则返回即撤销；状态按引用共享则必须显式撤销，且撤销与选择严格配对——放回位置在递归返回之后、return 之前。
• 同骨架三种返回风格：叶子打印（void）、叶子 return 1 + 内部 + 汇总（计数）、叶子返回布尔条件 + 内部 \|\| 汇总（判断）；bool 版用短路免费获得”找到即停”。
• 剪枝要趁早：在递归调用之前用约束检查砍掉不可能的分支（超重强制不拿），一行 if 常常省下半棵子树。
• 回溯解是”正确性优先”的暴力搜索：指数复杂度注定了它只适合小规模 n；看到大规模输入要立刻想到 memo/DP 这类优化方向。

常见陷阱与注意事项

1. 忘了 unchoose：共享容器（vector/数组）被上一层分支掏空或改坏，兄弟分支得到错误状态，结果可能”假阳性”（官方反例：删掉放回行后 {1,4,5,6} 误报可分）。规避：凡按引用修改状态，写完后立刻补还原语句，并用”两个分支都要正确”的用例测试。
2. 把 unchoose 写在 return 之后：那条语句永远不执行，等于没写。规避：还原必须发生在返回之前；若提前 return，先把还原语句复制到每个出口前面。
3. 短路被误用/漏用：a \|\| b 只在 a 为 false 时才执行 b——若两个分支都有必须执行的”收尾动作”（如各放回一个元素），把它们都包在递归调用内部或先算出两个 bool 再合并。官方指出：先 bool r1 = f(); bool r2 = g(); 再 r1 \|\| r2 会失去短路带来的早停。
4. 修改了按引用传入的调用方数据且不还原：即使算法正确，调用者的 vector 也被毁了。规避：要么只读 + 用下标游走，要么严格 choose/unchoose 配对。
5. 基准情形漏掉空输入/空容器：空集可分吗（两空桶和为 0 相等，答案是 true）？空物品的背包价值是 0？先想清楚边界再写代码。
6. 误用贪心代替搜索：0-1 背包按价值或 v/w 贪心都可能次优（官方两个反例）。规避：只要题目说”最大/最优 + 组合爆炸”，先按回溯枚举想，别默认贪心成立。
7. struct 定义细节：右花括号忘分号、定义在函数内部、成员名拼错。规避：struct 放函数外、}; 结尾、用 . 访问成员。
8. 在指数递归里埋 O(n) 操作（在开头删元素、每层复制整串）：n 稍大就慢到不可接受。规避：优先从容器末尾操作或改用下标参数。
9. 把”顺序无关”的子集当成”顺序有关”的排列去枚举：对 {a, b} 会同时生成 {a, b} 与 {b, a}，既重复又使规模从 2ⁿ 膨胀成 n! 量级。规避：子集决策树里元素顺序固定，每个元素只决策一次”要/不要”；只有真正讲究顺序的问题才用排列骨架。
10. 计数版基准情形 return 0 而不是 return 1：空子集也是合法子集，叶子应计 1；return 0 会让 countSubsets("") 输出 0（正确应为 1），并在更大集合上少算。规避：先在空输入上验证边界：countSubsets("") 应为 1、空集合的”子集存在和 target”问题要单独想清语义。

思考题（带答案）

问题 1：把示例 1 的 countSubsets 改成”bool 风格”：判断集合中是否存在某个子集，其元素之和等于给定目标值 target。只需要改动哪几处？ 答案：签名变为 bool subsetSumExists(const vector<int>& nums, int k, int sumSoFar, int target)：基准改为 if (k == nums.size()) return sumSoFar == target;；中间不再需要 + 计数，而是 return subsetSumExists(..., k+1, sumSoFar, target) \|\| subsetSumExists(..., k+1, sumSoFar + nums[k], target);（分别对应不选/选当前元素）。\|\| 的短路保证一旦某分支凑出 target，其余分支立即停止——这是”打印→计数→判断”三种返回风格切换的标准示范。 问题 2：官方演示过：把示例 2 中 rest.push_back(item)（unchoose）那一行删掉，{1,4,5,6} 这个本应返回 false 的输入会错误地返回 true。请解释为什么。 答案：没有放回，第一分支（把元素逐个试放进组 1/组 2）递归到底把 rest 掏空后就再没还原过。返回上层尝试”另一个组”时，rest 仍是空的，函数立刻命中基准 rest.empty()，拿当时半途的 sum1、sum2 直接比较——某个中间状态下两桶和恰好相等，于是误报 true。可见 unchoose 不是风格问题而是正确性要求：它保证每个分支看到的 rest 都是”自己该决策的那批元素”。 问题 3：0-1 背包回溯的最坏复杂度 O(2ⁿ) 何时出现？”超重只能不拿”的剪枝为什么能让最好情形降到 O(n)？ 答案：最坏出现在每个物品都轻于或等于剩余容量、每个节点都分裂出”拿/不拿”两个递归调用，形成满二叉树 2ⁿ 片叶子；最好情形是每件物品都超重，每个节点只有”不拿”一条分支，递归变成一条直线 O(n)。剪枝的本质是：装不下的选择不可能成为最优解的一部分，提前砍掉它既不影响正确性，又避免探索一整棵注定无解的子树。