企业官网建设流程全解析

回溯算法大概是面试里最容易“一看就会，一写就废”的题型。我刷到代码随想录 Day21 的时候，三道题连排：93 复原 IP 地址、78 子集、90 子集 II，正好把回溯的三种经典场景全占了——字符串切割、全量枚举、重复元素去重。这篇文章不打算把模板背一遍就完事，而是用三道题把“为什么这么写”彻底讲透，看完你能直接照着重写一遍，顺便把递归树打印的调试方法也学会。适合正在打基础刷题的人，也适合准备面试想快速捡起回溯的朋友。

好，开始。

1. 回溯问题的整体思路与三道题的定位

1.1 回溯算法的核心思想与套路模板

回溯说白了就是一棵隐式树的深度优先遍历。你在每个节点上做选择，往深处走，走不通就回头，换一条路再走。这个“回头”的动作就是回溯。它解决的问题都有一个共同特征：需要枚举所有满足条件的组合、子集或排列。

代码随想录里给的模板特别精简，我加了点自己的理解，变成四个要素：

• 选择列表：这一层 for 循环能选哪些元素。组合类问题通常用 startIndex 控制起点，排列类问题用 used 数组控制是否用过。
• 递归调用：选了当前元素之后，进入下一层，参数跟着变。
• 撤销操作：从当前分支返回时，把刚才加进 path 的元素弹出去，恢复现场。
• 终止条件：什么时候把当前 path 存进结果。组合题是长度够了，切割题是分割完成，子集题比较特殊，每个节点都要存。

模板长这样：

void backtrack(参数) { if (终止条件) { 存放结果; return; } for (int i = startIndex; i < nums.size(); i++) { path.push_back(nums[i]); // 处理节点 backtrack(新的参数); // 递归下一层 path.pop_back(); // 回溯，撤销本层 } }

这套模板的坑点不在模板本身，而在三个问题上：一是终止条件写在哪、怎么写；二是结果收集放在递归入口还是终止条件里面；三是循环里什么时候剪枝、什么时候去重。三道题正好各覆盖一个。

1.2 三道题放在一起的递进逻辑

为什么把这三道题放在同一天刷？因为它们的递进关系非常明显。78 子集是基础，让你理解“所有节点都是答案”这件事，这跟组合问题“只收集叶子节点”是完全不同的思路。90 子集 II 是在 78 的基础上加了重复元素，逼着你去处理去重。93 复原 IP 地址则是把回溯从“数组里选数字”上升到“字符串上做切割”，处理的是索引和边界。

我当时的感觉是：78 全懂了，90 就只是加了个排序和一行判断；90 搞定后，93 就是换了个收集结果的姿势，但终止条件反而更绕。所以建议你也按这个顺序刷，先 78 再 90 最后 93，会有种一路打通的感觉。

下面一道一道说。

2. 93 复原 IP 地址：字符串切割的边界与终止条件

2.1 题意拆解与切割思路

给一个只含数字的字符串，要求往里面插三个点，把它分成四段，每段都是合法的 IP 地址段。合法条件是：每段在 0 到 255 之间，且不能有前导零——除了数字 0 本身是合法的一段，像“01”这种就是非法。

比如“25525511135”可以切成“255.255.11.135”和“255.255.111.35”。“0000”只能切成“0.0.0.0”，因为“00”是非法前导零。“101023”能切成五种，这里就不全列了，后面调试部分会给完整输出。

这种题天然适合回溯。你每次截取 1 到 3 位数字作为下一段，截完用 isValid 检查一下，合法就往字符串里插个点，不合法就直接 break——为什么是 break 不是 continue？因为 IP 段最多三位，如果当前从 startIndex 截 i 位已经超了 255，那再往长截只会更大，后面的分支都不用看了。

2.2 递归结构与终止条件怎么定

很多人在终止条件这里犯迷糊。我用的是代码随想录的写法：pointNum 表示已经插了几个点。终止条件不是判断 startIndex 到了字符串末尾，而是判断 pointNum == 3。因为插满 3 个点后，还剩最后一段，需要单独截取并校验，校验通过才把整个串加入结果。

这里有一个隐藏边界：当 pointNum == 3 时，必须保证 startIndex < s.size()，也就是说最后一段不能是空串。否则像“255255”这种字符串，切成“255.255.”最后一段空，会被当成合法结果加进去，这就是个明显的 bug。

递归函数长这样：

参数：s（会被修改，插入点的字符串）、startIndex（本轮切割起点）、pointNum（已插入的点数）

核心循环：

for (int i = startIndex; i < s.size(); i++) { if (isValid(s, startIndex, i)) { s.insert(s.begin() + i + 1, '.'); // 在 i 后面插点 pointNum++; backtrack(s, i + 2, pointNum); // 点是间隔符，所以下一轮起点 +2 pointNum--; s.erase(s.begin() + i + 1); // 撤销插点 } else { break; } }

注意 insert 之后，原来下标 i 后面多了个点，所以下一次递归的 startIndex 要传 i + 2，而不是 i + 1。这个 +2 是我第一次写的时候最容易漏的点，漏了就死循环或者重复截取。

2.3 IP 段合法性校验：为什么不能直接用 stoi

isValid 函数看起来很简单，但我强烈建议别偷懒用 stoi，原因后面说。先看手写版本：

bool isValid(const string& s, int start, int end) { if (start > end) return false; if (s[start] == '0' && start != end) return false; // 前导零 int num = 0; for (int i = start; i <= end; i++) { if (s[i] > '9' || s[i] < '0') return false; // 非数字 num = num * 10 + (s[i] - '0'); if (num > 255) return false; // 超范围 } return true; }

为什么不直接用 stoi？两个原因。第一，如果截出来的是“25525511135”这种超长字符串，stoi 会直接抛出 out_of_range 异常，程序崩溃，你得先截短再转，麻烦。第二，stoi 没办法帮你判断前导零，比如“01”转出来是 1，看起来合法，实际 IP 段不允许。手写循环的时候，只要最高位是 0 且字符串长度大于 1，就一定能拦住。

2.4 复原 IP 地址最容易踩的三个坑

第一个坑是 insert/erase 的索引偏移。插入点之后，字符的位置整体右移，撤销的 erase 操作要传同一个位置。我见过有人 insert 用了 i + 1，erase 却传 i，结果字符串越删越乱。

第二个坑是终止条件里没检查剩余字符。pointNum == 3 时如果 startIndex 已经等于 s.size()，说明最后一段是空的，直接返回，不进结果。

第三个坑是循环里用了 continue 而不是 break。前面说了，截取长度从 1 到 3 逐渐增加。当长度为 3 时 num 已经超过 255，长度为 4 只会更大，所以不需要继续试探，break 能省掉所有无效分支。这个剪枝虽然不改变结果，但能让递归树小不少。

我也试过另一种写法：不用字符串插入，而是用 vector<string> ips 保存四段，递归结束后再把四段拼成完整的 IP。这种实现避免 insert/erase 的索引问题，思路更直观，性能也更好。下面给个精简版：

class Solution { public: vector<string> restoreIpAddresses(string s) { if (s.size() < 4 || s.size() > 12) return {}; vector<string> res, seg; dfs(s, 0, res, seg); return res; } void dfs(string& s, int start, vector<string>& res, vector<string>& seg) { if (seg.size() == 4) { if (start == s.size()) { res.push_back(seg[0] + "." + seg[1] + "." + seg[2] + "." + seg[3]); } return; } for (int len = 1; len <= 3 && start + len <= s.size(); len++) { string part = s.substr(start, len); if (!isValid(part)) continue; seg.push_back(part); dfs(s, start + len, res, seg); seg.pop_back(); } } };

这两种写法都行，个人更推荐 vector 版，逻辑清楚，只是拼接的时候注意别多拼点。刷题阶段如果你能两个版本都写一遍，对回溯的理解会更扎实。

3. 78 子集：在递归入口收集所有节点

3.1 子集与组合、排列的本质区别

先想一个问题：组合题“组合总和 III”是在什么时候收集结果的？是在 k 个元素都选完，也就是叶子节点的地方。而子集题不一样，[1]，[2]，[1,2] 这些中间状态通通都是答案。换句话说，组合问题的答案是树的叶子，子集问题的答案是整棵树的全部节点。

这个区别直接决定了代码里 result.push_back(path) 放在哪里。如果你的代码是先判断终止条件再收集结果，那最后收集的只有叶子，空集和中间子集全丢了。

排列问题的区别又不一样。排列不需要 startIndex，因为每个位置都能重新选其他位置的元素，所以要用 used 数组标记是否用过。子集和组合都用 startIndex 保证“后面的元素不回头选”，这样才不会产生 [1,2] 和 [2,1] 这种重复。

3.2 完整代码与收集时机分析

78 子集的完整实现：

class Solution { public: vector<vector<int>> subsets(vector<int>& nums) { vector<vector<int>> res; vector<int> path; dfs(nums, 0, res, path); return res; } void dfs(vector<int>& nums, int startIndex, vector<vector<int>>& res, vector<int>& path) { res.push_back(path); // 每个节点都是子集，先收集 if (startIndex >= nums.size()) return; // 没有可选元素就返回 for (int i = startIndex; i < nums.size(); i++) { path.push_back(nums[i]); dfs(nums, i + 1, res, path); path.pop_back(); } } };

注意第一行就是 res.push_back(path)，这一步已经在收集空集了。进入递归时 path 可能是空，可能是 [1]，可能是 [1,2]，每个状态对应一个子集，全部收进结果。然后才是判断 startIndex 是否越界。其实就算不写这个终止条件也能结束，因为 for 循环在 i 到达 nums.size() 时自然结束，但写上更清晰，也符合回溯模板的习惯。

3.3 复杂度与结果顺序

时间复杂度是 O(n * 2^n)。为什么乘 n？因为一共 2^n 个子集，每个子集都需要拷贝一份 path 到 res 里，拷贝一次最坏 O(n)。空间复杂度 O(n)，递归深度最多 n 层，path 存储 O(n)。

还有个细节：输出结果的顺序。以 [1,2,3] 为例，我写的递归会得到 [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]，这是按“前缀深度优先”的字典序，不是从小到大的字典序。LeetCode 只要求包含所有子集，不比较顺序，所以没问题。但如果题目要求字典序输出，你就需要收集完再排序，或者调整递归顺序。

4. 90 子集 II：排序去重的两种写法

4.1 重复元素为什么会生成重复子集

90 题给的是 [1,2,2]，数组中两个 2 是不同的元素，但对结果来说它们是不可区分的。如果你用 78 的代码直接跑，会得到 [[1,2(第一个2)], [1,2(第二个2)]] 这种视觉上重复的结果。

重复的根源在于：在同一层递归的 for 循环里，如果前面已经选过一个 2，后面又遇到一个相等的 2，那么从第二个 2 出发的所有分支，生成的子集跟前一个 2 的分支完全一样。

解决原则就一句话：先排序，让相等的元素相邻；然后在循环里跳过“同层已经处理过的重复元素”。

4.2 树层去重 vs 树枝去重

这是回溯去重里最经典的概念，很多人在这里绕晕。我用树来拆解。

• 树层：指的是同一个父节点下面的多个分支，也就是同一个 for 循环里的多次迭代。两个相同的元素如果出现在树层，那么第二个分支是第一个分支的重复，必须去掉。
• 树枝：指的是从根到某个叶子的单条路径，也就是递归深入的过程。路径上允许出现重复元素，比如 [1,2,2]，这是合法子集，因为两个 2 是数组里不同位置的两个值。

很多初次接触的人会把这两者搞混，写去重的时候连树枝的重复也一并砍掉，结果 [1,2,2] 这个正确结果就没了。记住：去重只去树层，不去树枝。

4.3 used 数组法与 startIndex 跳过法对比

代码随想录里给了两种写法，我都写出来对比一下。

第一种，used 数组法。需要额外维护一个 used 数组，标记当前递归路径上哪些元素已经用过：

class Solution { public: vector<vector<int>> res; vector<int> path; vector<vector<int>> subsetsWithDup(vector<int>& nums) { sort(nums.begin(), nums.end()); vector<bool> used(nums.size(), false); dfs(nums, 0, used); return res; } void dfs(vector<int>& nums, int startIndex, vector<bool>& used) { res.push_back(path); for (int i = startIndex; i < nums.size(); i++) { if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) { continue; // 同一树层的前一个相同元素没被使用，说明是本层重复 } path.push_back(nums[i]); used[i] = true; dfs(nums, i + 1, used); used[i] = false; path.pop_back(); } } };

这里的判断逻辑是：当前元素和前一个元素相等，且 used[i-1] 为 false，说明前一个相同元素不在当前路径上，它一定是本层 for 循环中已经处理完并回溯的元素，所以当前元素属于树层重复，跳过。如果 used[i-1] 为 true，说明前一个 2 在路径上，比如 [1,2,2] 这种情况，这是树枝上的合法重复，保留。

第二种，startIndex 跳过法。不需要 used 数组，直接比较下标：

class Solution { public: vector<vector<int>> res; vector<int> path; vector<vector<int>> subsetsWithDup(vector<int>& nums) { sort(nums.begin(), nums.end()); dfs(nums, 0); return res; } void dfs(vector<int>& nums, int startIndex) { res.push_back(path); for (int i = startIndex; i < nums.size(); i++) { if (i > startIndex && nums[i] == nums[i - 1]) { continue; } path.push_back(nums[i]); dfs(nums, i + 1); path.pop_back(); } } };

关键在 if (i > startIndex)，而不是 if (i > 0)。因为每次递归都会重置起点为 startIndex，如果写成 i > 0，会出现把合法的树枝重复也跳过的情况。只有 i > startIndex 才能精确表达“本层 for 循环里已经处理过 nums[i-1]”。

两种写法我实测下来，startIndex 法代码更短，used 数组法更通用——排列问题必须用 used 数组。建议都掌握，至少要能讲清楚为什么一个用 used[i-1]==false，一个用 i > startIndex。

4.4 去重最容易犯的错

第一个错是忘记排序。去重逻辑依赖相同元素相邻，不排序的话 [1,2,1] 里两个 1 不相邻，判断直接失效。所以先排序，这是前提，不是可选项。

第二个错是在循环里直接写 if (nums[i] == nums[i-1]) continue，而没加 i > startIndex 的判断。这样会把同一枝条内部的重复也拦掉，[1,2,2] 的叶子子集直接被砍掉。

第三个错是结果里出现重复元素，也就是根本没去重。检查方法很简单，跑一下 [1,2,2]，输出应该是 [[], [1], [1,2], [1,2,2], [2], [2,2]]，长度是 6。如果你输出里有两个 [2]，那就是去重没生效。关于这一块，后面《常见问题速查表》里我会把怎么检查列全。

5. 实操过程、调试技巧与常见问题速查

5.1 三道题的输出对照与自测用例

写题不能只看逻辑，要真的跑起来。我把三道题的关键自测用例和期望输出列成表，方便你对照调试。

这些输出我都是实际跑过验证的。特别是 101023 这个用例，覆盖了“0 单独成段”和“非 0 开头”的情况，非常适合回归测试。你写完代码后，先用这几个用例过一遍，再随机生成几个字符串测试，比如“123456789”这种没有合法切分的，确保结果是空数组而不是死循环。

5.2 状态打印法调试回溯

回溯题最怕找不着 bug。我调试这类题的固定套路是：在 dfs 入口打印当前层的信息，包括递归深度、startIndex、当前 path、以及关键变量。以 90 题为例：

void dfs(vector<int>& nums, int startIndex) { for (int i = 0; i < path.size(); i++) cout << " "; cout << "start=" << startIndex << " path=["; for (int v : path) cout << v << ","; cout << "]\n"; res.push_back(path); for (int i = startIndex; i < nums.size(); i++) { if (i > startIndex && nums[i] == nums[i - 1]) continue; path.push_back(nums[i]); dfs(nums, i + 1); path.pop_back(); } }

缩进随递归深度递增，一眼就能看到整棵递归树的形状。如果发现同一个 path 重复出现在兄弟分支，那大概率是去重条件不对；如果发现递归永远在往深处走，看看 startIndex 是不是忘了 +1；如果发现 path 里出现了从未选过的元素，回头检查撤销操作是不是漏了 pop_back。

这套方法对 93 题同样有效，只是打印的东西改成字符串和 pointNum。调试字符串切割时，我还会额外打印插入点之后 s 的当前完整串，这样能很快发现 insert 之后 startIndex 偏移错误的问题。

5.3 常见问题速查表

我把这三道题刷下来遇到的典型问题，总结成一个速查表。

这张表我建议直接存下来，笔试的时候碰到类似回溯题，先对照检查。

6. 扩展：子集问题不止回溯一种玩法

6.1 位运算枚举全部子集

回溯虽然是处理子集最通用的方法，但不是唯一方法。如果数组长度 n 比较小（一般不超过 20），位运算枚举更简单直接。把每个元素看成二进制的一位，1 表示选，0 表示不选，那么长度为 n 的数组的所有子集对应 0 到 (1<<n)-1 的所有整数。

for (int mask = 0; mask < (1 << n); mask++) { vector<int> subset; for (int i = 0; i < n; i++) { if (mask & (1 << i)) subset.push_back(nums[i]); } res.push_back(subset); }

这种写法没有递归，没有去重问题，代码非常短。但问题也明显：n 一旦超过 20，2^n 这个规模就基本执行不动了，而且它天然没有剪枝机制。回溯可以用约束条件提前砍掉大量分支，位枚举则必须枚举完所有状态。

6.2 回溯 vs 位运算怎么选

我平时的选择标准是：如果题目只让枚举所有子集且 n 很小，位枚举更快；如果题目带约束，比如“元素和不超过 target”或者“必须包含某个元素”，回溯剪枝优势就出来了。而且回溯能方便地处理去重，位枚举处理去重要先排序再对相同元素做特殊处理，麻烦得多。

另外还有一类题用的是状压 DP 里的子集枚举，比如给一个 mask，枚举它的所有子集。经典写法是这个：

for (int sub = mask; sub; sub = (sub - 1) & mask) { // 处理 sub }

这个循环每次会把 sub 跳到下一个 mask 的子集，时间复杂度是 O(2^k)，k 是 mask 中 1 的个数。很多状压 DP 题用它做状态转移。如果搜索热词里出现“状压 dp 枚举子集”，说的就是这件事，它和回溯完全不是一个赛道，但都属于“枚举子集”这个大的算法家族。

6.3 提两个容易混淆的热词

刷题圈最近流行“第 k 大子集和”，它跟上面说的子集枚举有交集，但考的是完全不同的技巧。核心办法通常是二分答案加计数，或者折半枚举（Meet in the Middle），n 大一点还要配合优先队列。如果哪天你看到“第 k 大子集和”这个热词，先去想二分答案能不能计数，别上来就回溯硬枚举，2^n 会直接超时。

还有“NASA 公开的 N-CMAPSS 数据集子集（DS02）”，这个跟算法题里的子集意思完全不一样。它说的是从完整数据集中抽出一部分样本做实验，属于数据处理范畴，跟回溯没有关系。搜索榜单里把这两个词放在一块，纯粹是“子集”这个关键词撞车了。

我个人实际刷完这三道题最大的体会是：回溯题的代码框架真的不难，难的是你愿不愿意画图。每次卡住，把递归树画出来，把每个节点的 path 写出来，问题基本就能定位。一个很小但很实用的建议：写之前先用纸笔把 78 题的递归树画出来，标注哪些节点要收集，哪些要跳过，这一步比编译运行十次都管用。

最后再分享一个我踩过的坑：第一次提交 93 题的时候，我用的是字符串插入法，isValid 判断完直接 insert，然后递归，但忘在递归调用的时候传 i + 2，而是传了 i + 1。结果就是每次插入点之后，下一轮又会用到点后面的数字，切出来的 IP 全是错的。所以如果你也用 insert 法，记住这个 +2 是关键，或者干脆换成 vector 收集段的方式绕开这个坑。

这三道题刷完之后，建议你顺手把 17 电话号码的字母组合、131 分割回文串再过一遍。它们分别是“不同集合的排列”和“字符串切割”的变体，跟这三道题合在一起，回溯的基本盘就算彻底拿下了。