企业官网建设流程全解析

把 Day18 的进度补上。今天练的主题是回溯（Backtracking），题目是 LeetCode 77 组合、216 组合总和 III、17 电话号码的字母组合。我的算法复健计划里，回溯阶段分了两轮：先把“组合类”问题打通，再进入排列、子集、棋盘类问题。77 是最标准的组合模板，216 等于在 77 的基础上多叠了一层“和等于指定值”的约束，17 则把思路从“在一个数字集合里挑”换成“按位置从候选字母表里选”。三道题放到同一天做，不光是因为它们都算回溯，而是因为它们能串成一条从“裸回溯”到“带约束回溯”的递进线。

如果你的情况跟我一样，属于看过不少题解、但自己一写就卡住的阶段，我建议按这个顺序刷：先 77 建骨架，再 216 学怎么把额外条件塞进递归参数，最后 17 感受字符串回溯和数字回溯的处理差异。这样到后面接触排列、子集、棋盘类问题时，回溯对你来说就是一个固定套路，而不是每次都要重新猜的魔法。

1. 为什么Day18把这三道题绑在一起练

1.1 回溯不是玄学，而是一棵递归树

我一直觉得回溯最劝退的地方，不是代码难写，而是“为什么这么写”很难讲清楚。其实回溯就是一种规范的暴力枚举：把整个搜索过程想象成一棵决策树，树的每一层代表一次选择，每个节点是当前已经做过的选择所组成的中间状态，从根到叶子的一条路径，就是一个完整的候选答案。

人到脑子枚举组合，最容易犯两个错误：漏掉分支，或者重复计算。递归树的好处是，只要你规定了每一层的选择范围，深度优先遍历会不重不漏地把所有路径走完。递归返回后再换下一条路，这个过程就叫回溯。很多教材喜欢用迷宫来比喻，我觉得更像玩那种“先在若干候选里选一步，走不通再回来换一步”的猜谜游戏。

所以回溯代码里最重要的三样东西是：终止条件、候选列表、撤销操作。终止条件决定什么时候记录一个答案；候选列表决定这一层能选什么；撤销操作决定递归返回后，当前状态能干净地回到上一层。

1.2 三题的递归树长得不一样

先看它们各自在递归树上的差别：

• LC 77：树深度由 k 决定，每一层都是从当前数字之后继续选数字，宽度是剩余数字的数量；
• LC 216：树深度也由 k 决定，但每一层除了继续选数字，还要保证当前路径的数字之和不超过目标值；
• LC 17：树深度由 digits 的长度决定，每一层的候选不是“剩余数字”，而是当前 digit 映射出来的几个字母。

区别看起来很细微，但对递归参数设计的影响很大。77 和 216 必须用一个 start 参数表示“下一层从哪个数字开始”，因为组合问题要求数字只能递增，避免出现 [1,2] 和 [2,1] 这种重复。17 则不同，每个位置独立，顺序由输入字符串固定，所以它必须用 idx 表示“当前处理到第几个数字”，而不能用 start。参数不同，本质上是因为“选择范围”的定义不同。

搞清楚这件事之后，再回头看我接下来写的代码，你会发现骨架惊人地相似，差别全在“状态变量”和“剪枝条件”上。

2. LC 77 组合：从递归树里把代码抄出来

2.1 先画 n=4, k=2 的递归树再动手

LC 77 题目描述很简单：给定 1 到 n 的 n 个整数，返回所有长度为 k 的组合。组合的意思是不考虑顺序，所以 [1,2] 和 [2,1] 算同一个答案。

我刷这题时没有立刻写代码，先在草稿纸上画了 n=4, k=2 的递归树：

第一层选 1：继续选 2,3,4，得到 [1,2] [1,3] [1,4] 第一层选 2：继续选 3,4，得到 [2,3] [2,4] 第一层选 3：继续选 4，得到 [3,4] 第一层选 4：后面没有数字可选，不产生答案

从画出来的树里能看到两个关键信息：

1. 下一层可选范围必须是“上一层选的数字 + 1”之后的所有数字，这样才能保证组合是递增的；
2. 第一层选 4 是明显没意义的分支，因为它后面已经没有足够多的数字来凑齐 k=2 个。

第一点对应代码里的 start 参数。很多人可能会想，用 visited 布尔数组来防止重复选择，像做排列那样。但组合用不到，因为组合只在乎集合，不在乎顺序。有了 start 参数，搜索空间天然被砍掉一半以上。举个例子，如果第一层选了 2，下一层就从 3 开始；如果用了 visited，你还得去考虑 1，但 [2,1] 在组合里是非法重复。

2.2 剪枝：循环上界是怎么推出来的

第二点对应剪枝。最笨的回溯写法，循环从 start 到 n 全部扫一遍，然后在递归内部判断“剩余数字够不够”。这种写法也能过，但学习阶段我更建议直接把剪枝写进循环边界，理解起来更清晰。

假设当前 path 里已经选了 p 个数字，目标长度是 k，那么我们还需要 r = k - p 个数字。当前循环变量是 i，从 i 开始到 n 一共有 n - i + 1 个数字可用，至少要大于等于 r，才有继续递归的必要：

n - i + 1 >= r => i <= n - r + 1

所以循环可以写成：

for (int i = start; i <= n - (k - path.size()) + 1; ++i)

以 n=4, k=2 为例，初始 path 为空，r=2，因此第一层循环 i 最大是 4 - 2 + 1 = 3，直接跳过 i=4。这个剪枝特别适合大 n 的场景，比如 n=20, k=5，如果第一层选了 18，后面能选的数字最多 19、20 两个，根本凑不满 5 个，这个分支就不该进入。

2.3 完整实现和从这题里沉淀出来的模板

LC 77 的完整 C++ 实现如下：

class Solution { public: vector<vector<int>> combine(int n, int k) { vector<vector<int>> ans; vector<int> path; dfs(n, k, 1, path, ans); return ans; } void dfs(int n, int k, int start, vector<int>& path, vector<vector<int>>& ans) { if (path.size() == k) { ans.push_back(path); return; } int need = k - path.size(); for (int i = start; i <= n - need + 1; ++i) { path.push_back(i); dfs(n, k, i + 1, path, ans); path.pop_back(); } } };

这题值得沉淀的点有两个。第一个是“三段式”写法：先 push_back，再递归，最后 pop_back，这三行一定要当成一个整体写。有些初学者会写完递归后忘记 pop_back，或者因为中途 return 导致流程混乱，最终 path 越来越长，答案长度越来越离谱。第二个是“答案只在叶子节点收集”：当 path.size() == k 时，path 就是一组完整答案，这时不管最终答案对不对，都要 return，否则 path 还会接着塞更多元素。

时间复杂度是 O(k * C(n, k))，因为组合总共有 C(n, k) 个，每收集一个答案要拷贝一份长度为 k 的 path。空间复杂度是 O(k)，不算输出数组。

3. LC 216 组合总和 III：把“额外约束”塞进递归参数

3.1 题目和 77 的差异在哪

LC 216 组合总和 III 可以看成 LC 77 的加强版：候选数字从 1 到 9，固定不变，要选出 k 个数字，并且这 k 个数字的和要等于 n。因为数字不可重复且不考虑顺序，所以仍然是组合问题，仍然需要用 start 参数。

唯一多出来的状态是“当前路径的和”。我处理这类问题时，习惯不在递归外面维护一个 sum 变量，而是直接把目标值递减传递。也就是说，递归函数里加一个参数 remain，表示“还需要凑多少和”。

这样做的好处是代码直观。递归一层，如果 choose 了数字 i，下一层就调用：

dfs(k, remain - i, i + 1, path, ans);

因为 remain 是以值传递方式传下去的，当前层的 remain 不会被修改，所以递归返回后不需要像 sum 那样手动减回来。

3.2 剪枝条件的优先级

LC 216 虽然数字范围只有 1 到 9，但剪枝依然重要，不然会出现大量注定失败的递归。我按照优先级把这些剪枝条件排了个序：

1. path.size() == k 时，必须马上判断 remain 是否为 0，是则记录答案，否则直接返回；
2. remain < 0 时，说明已经超过目标和，当前路径不可能合法，直接返回；
3. 循环里如果 i > remain，直接 break。因为数字是递增排列的，后面的数字更大，更不可能凑出剩余需要的和；
4. 循环里还要判断剩余数字是否够用：如果 9 - i + 1 < k - path.size()，也直接 break。原因和 77 的剪枝一样，当前可用的数字数量已经不够填满 path。

注意第 3、4 条为什么是 break 而不是 continue。因为循环是从小到大遍历数字的，i 越大，数字越大、剩余数量越少，两个条件是单调变差的，所以一旦当前 i 不满足，后面所有 i 都不满足，用 continue 只会白白多跑几次循环。

完整代码：

class Solution { public: vector<vector<int>> combinationSum3(int k, int n) { vector<vector<int>> ans; vector<int> path; dfs(k, n, 1, path, ans); return ans; } void dfs(int k, int remain, int start, vector<int>& path, vector<vector<int>>& ans) { if (path.size() == k) { if (remain == 0) { ans.push_back(path); } return; } if (remain < 0) return; for (int i = start; i <= 9; ++i) { if (i > remain) break; if (9 - i + 1 < k - static_cast<int>(path.size())) break; path.push_back(i); dfs(k, remain - i, i + 1, path, ans); path.pop_back(); } } };

我在入口的地方没有做太多防御判断，比如k > 9、n < k*(k+1)/2之类，因为循环和 remain 会把它们自然过滤掉。但如果你想让函数更快返回，也可以在最外层加这些判断。不过学习阶段，我更推荐把边界情况留着，跑几个用例感受一下回溯是怎么自然排除非法输入的。

3.3 LC 216 里容易忽略的边界

有几个边界容易踩。第一个是 k 很大、n 很小的情况。比如 k=3, n=6，理论上 1+2+3=6，答案存在，但如果你把剪枝写成if (remain < 0) return;没问题；可如果你用累加 sum 并判断if (sum > n) return;，同样没问题。怕的是把“当前和”写进剪枝条件但又没有正确维护，导致明明 1,2,3 就能凑够，却因为路径顺序问题提前剪枝了。

第二个是 0 和 1 对结果的影响。LC 216 的输入 k 通常是大于等于 1 的，但如果 k=0，path.size() == k 在一开始就成立，会先收集一个空数组。这个取决于题目要求，做竞赛或者面试时要先看清约束。第三个是使用static_cast<int>(path.size())这种细节，C++ 里 size() 返回无符号数，和 int 做比较时有符号转换风险，虽然这个规模下不太会出问题，但养成好习惯没坏处。

4. LC 17 电话号码的字母组合：从选数字切换到按位映射

4.1 为什么这题不能用 start 参数

LC 17 输入是一串数字，比如 "23"，要求把每个数字映射到对应的字母，输出所有字母组合。按题目给的映射，2 对应 "abc"，3 对应 "def"，所以结果是 "ad"、"ae"、"af"、"bd"、"be"、"bf"、"cd"、"ce"、"cf"。

这题如果按 LC 77 的习惯直接套 start 参数，思路会卡住。因为 LC 17 里，每一层的候选集合完全不一样：第一层只能从 digits[0] 映射的字母里选，第二层只能从 digits[1] 映射的字母里选。start 参数只能用来控制“从同一个大集合的哪个位置开始”，它管不了“不同层有不同集合”这件事。

所以这题的递归参数要换成 idx，表示当前处理到 digits 的第几个位置。递归树长这样：根节点下面有三个分支，对应第一个数字的三个字母；每个分支下面又有三个分支，对应第二个数字的三个字母。叶子节点的数量就是所有组合的数量。

核心理解点：LC 77 的 start 参数是为了去重，LC 17 天然不需要去重，因为每一位的来源是固定且独立的。上一层的选择不会影响下一层可选项的范围，下一层总是从对应数字的映射里选，因此只需要一个位置指针。

4.2 字符路径的拼接和回退

路径类型从 vector 换成了 string，但操作逻辑完全一致：push_back 一个字符，递归，pop_back。完整 C++ 代码：

class Solution { private: vector<string> mp = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; public: vector<string> letterCombinations(string digits) { if (digits.empty()) return {}; vector<string> ans; string path; dfs(0, digits, path, ans); return ans; } void dfs(int idx, const string& digits, string& path, vector<string>& ans) { if (idx == digits.size()) { ans.push_back(path); return; } int d = digits[idx] - '0'; for (char c : mp[d]) { path.push_back(c); dfs(idx + 1, digits, path, ans); path.pop_back(); } } };

这里要注意输入是 "23" 这种字符串，路径长度始终等于 digits.size()。当 idx == digits.size() 时，说明已经处理完所有数字，此时 path 里已经积累了一位对应一个字母，把它作为答案记录下来。因为 path 是按引用传的，所以在记录之前一定要拷贝，C++ 里ans.push_back(path)本身就会拷贝，不需要额外处理。但如果你用 Python，就得写成ans.append(path[:])，否则后续 pop_back 会污染已存的答案。

另外，题目对输出顺序有要求，通常是字典序。这个顺序来自两方面：一是映射表 mp 内部按字母顺序排列，二是 for 循环从左到右遍历。只要不把映射表顺序打乱，结果就会自然满足题目要求。

4.3 空字符串和非法输入的防御

LC 17 最容易翻车的测试用例是输入空字符串。如果 digits 为空，应该是[]，而不是[""]。因为在组合问题里，空字符串算一个答案，但对电话号码来说，没有数字自然没有字母组合，所以必须在入口处直接判断：

if (digits.empty()) return {};

至于输入中出现 0 或 1，题目一般不会给这种用例，因为 0 和 1 没有对应字母。如果真出现了，我的 mp 里对应位置是空字符串，for 循环一次都不执行，自然不会产生任何答案。这个行为从逻辑上是自洽的，但为了清晰，也可以显式判断一下 mp[d] 为空就直接 return，不过对 LeetCode 17 来说不是必须的。

5. 把三道题的递归参数和剪枝放在同一张表里

5.1 参数设计的横向对照

刷完这三道题，我最强烈的感受是：回溯题并不需要你创造什么新知识，只需要弄清楚“当前状态由哪几个变量定义”。我把三题的参数整理成一张表：

表里能看到，77 和 216 的参数非常接近，唯一的区别是 216 多了一个 remain。很多学回溯的人觉得 216 难，难在哪里？不是代码难，而是六个参数堆在一起，容易忘记哪个变量管什么。我的建议是给每个参数写一句话注释：start 表示下一层从哪个数字开始，remain 表示还需要凑多少和，path 表示已经选择的数字。写完注释再写代码，思路会清晰很多。

LC 17 的参数相对更简，因为选择范围完全由原始输入决定。它更像一个“按位枚举”的问题，每个位置有几个选择，结果就是几叉树。

5.2 复杂度分析与剪枝收益

先看复杂度，这也是面试里容易突然被问到的问题。

LC 77 的时间复杂度是 O(k * C(n, k))，空间复杂度 O(k)。C(n, k) 是组合总数，每个答案要拷贝 k 个元素。很多人会把答案数组本身的大小算进空间复杂度，严格来说是额外输出空间，不计入辅助空间，所以空间复杂度只算递归栈和 path。

LC 216 的候选集固定 1 到 9，因此组合总数上界是 C(9, k)，又受到 n 的限制，实际会小很多。时间复杂度 O(k * C(9, k))，空间 O(k)。这题剪枝的价值主要在于避免那些“数字数量够但和已经超了”的无效分支，运行时间提升非常明显。

LC 17 的复杂度要按位算：设 digits 长度为 m，每个数字最多映射 4 个字母，叶子数量不超过 4^m，每个答案长度为 m，时间复杂度 O(m * 4^m)，空间复杂度 O(m)。

我不建议死记这些公式。比较实用的理解方式是问自己：这棵递归树到底有多少个叶子，每个叶子的深度是多少。树的叶子决定了答案数量，深度决定了复制答案的成本，两者相乘就是时间复杂度的核心部分。剪枝做的事情，就是让原本可能存在的分支在还没长到叶子之前就被砍掉。

6. 回溯复健踩坑清单：我被坑过三次的地方

6.1 忘记撤销是最隐蔽的 bug

回溯题写多了之后，最常见的错误不是边界条件，而是少了一次 pop_back。画一个很简单的场景：LC 77 里，第一条路径选 [1,2]，递归返回后如果忘记把 2 弹掉，下一轮 path 就变成 [1,2,3]，长度已经等于 k=2？不对，长度是 3，根本进不了收集答案的分支，于是整个循环直接空转。

你可能会想，那我把终止条件改成path.size() >= k不就绕过去了吗？这确实是很多初学者“修 bug”的方式，但它会掩盖问题。正确的做法是把三段式操作刻在脑子里：

path.push_back(i); dfs(...); path.pop_back();

任何一次 push，都必须对应一次 pop，哪怕递归里提前 return 也一样。注意我这里的说法：如果递归里有提前 return，调用方依然会在 dfs 返回后执行 pop_back，所以不要因为在递归内部看到 return 就手忙脚乱，只要调用方把“递归后撤销”这一行放在正确位置，大部分情况都是安全的。

6.2 剪枝条件写在循环里还是函数开头

剪枝的位置没有绝对标准，但我个人比较喜欢分两层：

大剪枝写在函数开头，比如 LC 216 的if (remain < 0) return;。这种剪枝负责尽早终止已经不可能成功的整个子树。细剪枝写在 for 循环内部，比如 216 的if (i > remain) break;。这种剪枝负责把当前层后续明显无意义的候选跳过。

为什么要分两层？因为递归入口的剪枝更通用，不管当前循环从哪开始，只要状态本身已经非法，就没必要再进循环。而循环内部的剪枝依赖具体的 i，可以更精准地砍掉前面和后面的候选。

写剪枝时还要注意不要过度剪枝。我一开始写 LC 216 时就是多加了一个“当前和已经超过 n 就 return”，但当时我用的是累加 sum 而不是 remain，结果 sum 传值传错了位置，导致合法答案被剪掉。把状态参数写清楚，再从状态推剪枝条件，比“凭感觉加 if”可靠得多。

6.3 递归复健最好用的调试方法

刷回溯题，调试方法比很多花哨工具都好用：打印缩进和 path。我一般在 dfs 开头加一行：

cout << string(depth * 2, ' ') << "path: "; for (int v : path) cout << v; cout << "\n";

然后递归调用时 depth + 1。这样能看到每一层进入递归时的状态。比如 LC 77，你能清楚看到 path 从 [1] 到 [1,2]，再回到 [1]，再到 [1,3]。整个“选择-递归-撤销”的过程被可视化之后，脑内模拟困难的问题一下就清楚了。

第二步是做一个“五问”检查清单，每次写回溯前先口头回答一遍：

1. 这一层选择什么？
2. 下一层从哪里开始？
3. 达到什么条件才有资格记录答案？
4. 哪些情况直接不需要进入递归？
5. 做选择和撤销选择的代码是否配对？

用这三道题各自回答一遍，就会变成：

• LC 77：这一层选数字 i，下一层从 i+1 开始，path.size() == k 时记录，数字不够填满时不进入递归，push 和 pop 配对；
• LC 216：同样选数字 i，下一层从 i+1 开始，但多了一个 remain，path.size() == k 且 remain == 0 才记录，i > remain 或数字不够时剪枝，push 和 pop 配对；
• LC 17：这一层选字母 c，下一层 idx+1，idx == digits.size() 时记录，输入为空字符串时不进入递归，push 和 pop 配对。

这套检查清单看起来简单，但真到做题紧张的时候，能帮你把思维的顺序固定下来，不会东想西想。

最后分享一个我自己的习惯：这三道题里最值得反复默写的是 LC 77。第二次刷的时候不要看题解，直接在编辑器里写出剪枝后的循环边界。如果你能在五分钟内把i <= n - (k - path.size()) + 1这个条件和三段式代码完整写对，说明回溯的骨架已经长在脑子里了。那时候再去看 216 和 17，会顺很多很多。