企业官网建设流程全解析

代码随想录Day21那天，回溯专题终于从组合问题迈进了切割和子集的范畴：93.复原IP地址、78.子集、90.子集II。如果你也是跟着Carl的刷题路线在走，会发现前几天的组合问题练的是“从n个元素里选k个”，而这三题把回溯的另外两个经典形态一次性端了出来——切割问题和子集问题。这篇文章就是我的完整复盘，适合正在跟代码随想录的读者，也适合所有对回溯似懂非懂、一写就错的人。

先说结论：这三道题放在同一天是非常有讲究的。它们共用同一套回溯模板，但分别考了三个维度的变化——切割问题如何定义状态、子集问题在哪里收集结果、集合里有重复元素时如何做树层去重。把这三个维度想清楚，回溯基本就打通了一半。

1. 回溯为什么是“穷举的艺术”：先建好那棵树

很多人在刷回溯题的时候，背模板背得滚瓜烂熟，但一换题就傻眼。原因很简单：模板只是骨架，你并没有想清楚这棵树长什么样。回溯算法本质上就是在一棵递归树上做深度优先遍历，每个节点代表一个“已经做出的选择”，每一条边代表“下一次可选的选项”。所谓穷举，不是无脑递归，而是把整个搜索空间组织成一棵树，然后用一套固定的方式去遍历它。

这套方式就是刷题圈人人都会背的三件套：递归进入、循环展开、回退还原。调用层数越深，能选择的范围越小，到某个边界就返回，返回时把之前做过的选择撤销掉。整个过程和操作系统里函数调用的栈机制一模一样——每一次递归调用都对应一次压栈，返回对应弹栈，撤销状态对应恢复栈帧。所以很多资料里管回溯叫“backtrace栈回溯”，这个叫法不是修辞，而是实打实的运行机制。

1.1 一套模板走天下：递归进入、循环展开、回退还原

把回溯模板写成伪代码，是这样一份结构：

void backtracking(参数列表) { if (终止条件) { 收集结果; return; } for (选择 : 本层集合中的元素) { 处理节点; backtracking(更新后的参数); 撤销处理; } }

这四行里，“处理节点”是往下走一步，“撤销处理”是退回来，for循环负责横向枚举这一层所有合法的选择，递归负责纵向往下扩展。少了任何一环，要么递归无限深入，要么状态错乱导致结果重复或缺失。

我见过很多人写撤销处理时只写了push，忘了pop；或者在某条提前返回的分支里没做撤销，导致上一层状态被污染。这事儿在Day21的三道题里特别致命，尤其93题这种需要在字符串里插入字符再删掉的题，稍不留神就会把两个点叠在一起。

1.2 切割与子集，本质上是同一种“位置枚举”

Day21之前练的组合问题，比如77.组合、216.组合总和III，可以理解成“从可选集合中挑元素”。但是切割和子集这两个词，术语上容易让人迷糊。我自己当时的顿悟点在这里：切割问题和子集问题，本质上都是在枚举“位置”。

切割问题里的“位置”，是下刀的位置。字符串一共n个字符，就有n-1个可以下刀的地方，每次决定哪里切一刀，和组合问题决定“选哪个数”在数学结构上没有区别。子集问题里的“位置”，是数组中每个元素“选还是不放进去”的分叉点，本质上也就是在每个下标处做一次二选一。所以三题的递归树其实是同一类结构，区别只在于两个细节：结果收集的时机，以及状态边的含义。

这也是为什么回溯模板里的终止条件和收集结果的位置特别关键。组合问题通常只在叶子节点收集，切割问题在满足边界的中间节点收集，子集问题则是全节点收集。代码位置差一行，输出的结果就会从“一个全集”变成“一堆碎片”。

2. 93.复原IP地址：不是选数字，而是连续切三刀

93题给的是这样一个场景：给你一个只含数字的字符串，比如“25525511135”，把它还原成所有合法的IPv4地址。所谓合法，就是四个片段，每段必须是0到255之间的整数，并且不能有前导零。

很多初学者第一个思路是“选四个数字拼出来”，每个片段随便取几位，然后检查。这个思路不能说错，但代码很容易写得又臭又长，因为你是在同时枚举“选哪一段”和“这一段多长”。换成切割思路一下就顺了：你不用管四个片段最终是谁，只需要在字符串里切三刀。切完之后如果四段都合法，就是一个答案。

三刀怎么切？第一刀可以插在第1个字符到第3个字符后面，第二刀紧跟其后，第三刀同理。每一刀的位置都依赖上一刀的位置，天然就是回溯要处理的问题。

2.1 状态机设计：startIndex与pointNum两个变量就够了

93题的状态变量比组合问题多一个，但没有本质变化：

• startIndex：当前这一段从哪个下标开始。第一刀在startIndex之后切，切完之后下一段的起点变成i + 2，因为第i位后面插了一个点。
• pointNum：已经插了几个点。这个变量用来控制终止条件。

终止条件设定为pointNum == 3，这时候字符串里已经插好了三个点，剩下的事情就是检查第四段（也就是startIndex到字符串末尾这一段）是否合法。合法就收进结果，不合法就弹回去。

这里有个让很多人困惑的点：为什么不是枚举到i == s.size()才终止？因为IP地址固定只有四段，你不需要切到字符串末尾才知道成不成立。插完三刀之后，剩下的整段天然就是第四段，直接检查就行。这样写代码也最简洁。

2.2 IPv4片段合法性检查的四个硬条件

切割点选好了，还是需要判断“从startIndex到i”这段子串能不能作为一个合法片段。我按代码随想录的思路，把合法性判断封装成isValid函数，四个条件按顺序写：

bool isValid(const string& s, int start, int end) { if (start > end) return false; // 前导零：只有“0”本身可以，像“01”“012”都不行 if (s[start] == '0' && start != end) return false; // 长度限制 if (end - start + 1 > 3) return false; int num = 0; for (int i = start; i <= end; i++) { if (s[i] < '0' || s[i] > '9') return false; // 虽然题目给的是数字串，防御性写上 num = num * 10 + (s[i] - '0'); if (num > 255) return false; } return true; }

前导零这个坑一定要单独说。字符串“010”里面，片段“010”转换成整数是10，看着好像合法，但IPv4地址规范不允许“010”这种写法。如果你用stoi转完再去比较，等于把这个不合法的情况“洗白”了，最终会得到一堆带前导零的错误地址。这也是我建议直接在字符串层面判断，而不是先转整数再判断的原因。

2.3 避免重复分割的原生剪枝与显式剪枝

93题本身状态空间很小，四层递归，每层最多选3种长度，理论分支数在3的4次方数量级，也就是81种，暴力跑完全没问题。但题目数据稍微变长，不加剪枝就会开始浪费时间。这里有两种剪枝手段，我建议都加上。

第一种是循环内剪枝。每一段最多只能取1到3位，所以循环里i最多到startIndex + 2，超过这个范围直接break。同时，如果从startIndex开始当前这段已经非法，比如大于255，那再往后延长只会更大，直接break而不是continue。这能砍掉大量无效分割。

第二种是进入for循环之前做整体判断。字符串剩余长度必须能填满还没生成的片段，也不能超出容量：

int remain = s.size() - startIndex; int needMin = 4 - pointNum; // 还需要至少每段1位 int needMax = (4 - pointNum) * 3; // 最多每段3位 if (remain < needMin || remain > needMax) return;

比如还剩两段没切，但剩余字符只有1个，那无论如何也凑不出两个合法片段；反过来剩余字符超过6个，也一定填不满两段各3位。这个剪枝在startIndex不断后移的过程中非常有效，实际跑起来大部分分支在进入递归前就会被拦下来。

2.4 在字符串上“插点”的操作细节

切割题的常见实现有两种，代码随想录的标准做法是在原字符串上直接插入点号，递归完了再删掉。另一种做法是拿一个vector 暂存四段，到最后再拼成带点的字符串。两种写法都可以，但它们的代码风格差别很大，我建议新手优先学第一种，因为它在操作上更贴近“切割”这个语义。

核心就两句：

s.insert(s.begin() + i + 1, '.'); backtracking(s, i + 2, pointNum + 1); s.erase(s.begin() + i + 1);

为什么递归参数是i + 2？因为第i个字符后面被插入了一个点，那么这个点本身占一个位置，下一段的起点自然就变成i + 2。撤销操作要删掉同一个点，后面无论递归多深，只要回到这一层，这个点就在这个位置。

完整代码长这样：

class Solution { private: vector<string> result; bool isValid(const string& s, int start, int end) { if (start > end) return false; if (s[start] == '0' && start != end) return false; if (end - start + 1 > 3) return false; int num = 0; for (int i = start; i <= end; i++) { if (s[i] < '0' || s[i] > '9') return false; num = num * 10 + (s[i] - '0'); if (num > 255) return false; } return true; } void backtracking(string& s, int startIndex, int pointNum) { if (pointNum == 3) { if (isValid(s, startIndex, s.size() - 1)) { result.push_back(s); } return; } for (int i = startIndex; i < s.size(); i++) { if (!isValid(s, startIndex, i)) break; s.insert(s.begin() + i + 1, '.'); backtracking(s, i + 2, pointNum + 1); s.erase(s.begin() + i + 1); } } public: vector<string> restoreIpAddresses(string s) { result.clear(); if (s.size() < 4 || s.size() > 12) return result; backtracking(s, 0, 0); return result; } };

如果坚持用vector 暂存字段，最后的拼接就变成把四个字段用"."连起来。这写法的好处是字符串操作更安全，不会出现insert和erase位置搞错的问题，坏处是多了一层拼接逻辑，而且字段必须在递归最深时才知道是否合法，代码读起来不如插点法直观。实测下来，插点法的Bug集中在“忘了erase”和“写了i+1而不是i+2”，这两个点我在本地调试时各踩过一次，写代码时盯紧就行。

3. 78.子集：为什么收集结果要放在递归的最前面

78题很简单：给一个不含重复元素的整数数组，返回所有子集。示例：输入[1,2,3]，输出[[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]。注意，空集和数组本身都算子集。

这道题的代码量比93题少很多，但它在回溯里的地位不亚于组合题，因为它把“结果收集”这个动作的位置问题带出来了。组合题通常在终止条件里收集结果，子集题则是在每一次进入递归时先收集当前path。

3.1 递归树里所有节点都是答案

为什么子集要在进入递归时立刻收集？因为子集的定义决定了：任何一个中间节点代表的“已选元素集合”都是一个合法子集。空集是第一个节点，选择了第一个元素后的[1]也是一个节点，继续往下扩展的[1,2]还是一个节点，哪怕最后没有走到叶子，这个节点本身也是答案。

代码随想录的题解里有一句话我印象很深：如果把组合问题比作“只收集叶子”，子集问题就是“收集所有节点”。所以收集结果的代码必须放在递归函数的第一行，而不是放在终止条件里。

void backtracking(vector<int>& nums, int startIndex) { result.push_back(path); // 关键：进入就收集 for (int i = startIndex; i < nums.size(); i++) { path.push_back(nums[i]); backtracking(nums, i + 1); path.pop_back(); } }

这个版本我甚至没有写终止条件。for循环自然结束就返回了，所以递归到startIndex等于数组长度时，不会进入任何分支，自动返回。这种写法在子集类题目里非常常见，因为天然不需要额外的return条件。

3.2 隐式终止：把return写出来会发生什么

有一种非常容易犯的错误，是把终止条件写成这样：

if (startIndex >= nums.size()) { result.push_back(path); return; }

看起来好像很严谨，但结果会漏掉大量非叶子节点。比如递归到了叶子[1,2,3]再返回，你才发现[1,2]这个中间节点在叶子之前根本没有被记录过。你最后得到的结果会只剩“从某个路径走到底的全部元素组合”，而不是“所有前缀拼接的集合”。

这是子集题和组合题最大的不同。写组合题时，终止条件伴随收集结果已经成为肌肉记忆，做子集题时会不自觉地把result.push_back(path)放进if里，结果一跑就少几个子集，调试半天才发现收集位置错了。我建议自己推演一遍[1,2,3]的递归树，把每个节点手动标出来，你会立刻明白为什么收集要放在递归函数开头。78题结果顺序很规整：[]、[1]、[1,2]、[1,2,3]、[1,3]、[2]、[2,3]、[3]，这个顺序和自己手推的递归树完全吻合，拿来验代码逻辑非常方便。

复杂度方面，生成全部2^n个子集是不可避免的输出开销，每个子集平均长度O(n)，所以时间至少是O(n * 2^n)；回溯本身每走一步做一次push/pop，常数很小。空间复杂度O(n)的递归栈深，外加结果集占用的O(n * 2^n)输出空间。

4. 90.子集II：同一层去重，而不是同一条路径去重

90题是78题的加强版，唯一的区别是数组里可能包含重复元素。示例：[1,2,2]，要求输出所有不重复的子集。答案里有[2]、[2,2]、[1,2]，但没有两个不同的[2]——因为两个2长得一样，取哪个2都算同一个子集。

去重一旦出现，回溯就多了一个核心考点：到底在哪个维度上去重。是“同一条路径上的重复”，还是“同一层选择里的重复”？搞不清这个，代码就会要么去不掉重复，要么把本来合法的子集也误杀了。

4.1 排序是第一前提

90题去重的第一步是给数组排序。这个动作不是可有可无的，它决定了去重判断能否成立。

只有排序之后，所有相同的元素才会相邻排列，你在遍历时才能通过“当前元素和前一个元素相等”来判断要不要跳过。如果不排序，相同元素散落在数组各个位置，用下标做相等判断就完全失效。

sort(nums.begin(), nums.end());

排序的时间成本是O(n log n)，对整体复杂度没有实质影响，所以放心排。

4.2 used数组到底在“记录”什么

代码随想录里对去重的解法通常使用一个vector used数组，标记一个元素是否已经在当前路径中被使用。在for循环里，去重的关键判断是：

if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) { continue; }

这里最容易被绕晕的就是used[i - 1] == false这个条件。为什么要求前一个相同元素“未被使用”才跳过？因为used[i - 1] == false意味着前一个相同元素不是当前路径的祖先，它和nums[i]属于同一个父节点下的平行分支。这种情况下如果选择nums[i]，生成的结果会和“选择nums[i - 1]”那一支的结果完全重复，所以必须跳过。

反过来，如果used[i - 1] == true，说明前一个相同元素就在当前这条递归路径上，比如第一层选了第一个2，下一层递归时看到第二个2，前一个2标记为true，这时候不跳过，才能生成包含重复值的合法子集[2,2]。

一句话总结：used[i - 1] == false是树层去重，used[i - 1] == true是树枝去重。90题要的是树层去重，因为[2]这个子集只需要出现一次，而[2,2]是另一个不同子集，必须保留。

4.3 另一种写法：i > startIndex完成等价去重

90题还有另一种常见的去重写法，不需要used数组：

if (i > startIndex && nums[i] == nums[i - 1]) { continue; }

这里i > startIndex的判断，等价于“nums[i - 1]不是本层起始元素”。仔细想一下，startIndex是这一层第一个可以选择的元素下标，当i等于startIndex时，i-1属于上一层路径或者根本不在选择范围内，此时即使nums[i]和nums[i-1]相等，也不能跳过——因为这是分支的起点，当前子集还没选过这个值。只有当i > startIndex时，说明i-1已经在当前for循环里被处理过了，这时再遇到重复值才需要跳过。

这两套写法的去重效果完全一样。used数组版本更通用，尤其当题目状态复杂时，used数组还能用于其他判断（比如排列问题）；i > startIndex版本更轻量，理解起来也更直观。代码随想录主线用的是used数组，所以我建议优先啃下used数组版本，明白它之后再看i > startIndex版本，会瞬间通透。

90题完整代码如下：

class Solution { private: vector<vector<int>> result; vector<int> path; void backtracking(vector<int>& nums, int startIndex, vector<bool>& used) { result.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; backtracking(nums, i + 1, used); used[i] = false; path.pop_back(); } } public: vector<vector<int>> subsetsWithDup(vector<int>& nums) { sort(nums.begin(), nums.end()); vector<bool> used(nums.size(), false); backtracking(nums, 0, used); return result; } };

如果你用i > startIndex版本，可以去掉used数组：

void backtracking(vector<int>& nums, int startIndex) { result.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]); backtracking(nums, i + 1); path.pop_back(); } }

我个人在比赛和面试中更喜欢用i > startIndex版本，因为它不需要额外维护一个数组，代码短，也不容易在递归里忘记重置used状态。但如果你正在跟代码随想录，我还是建议把used数组版本彻底弄懂，因为后面很多回溯题都会用这个套路，提前打好基础不吃亏。

5. 三题放一起的复盘：状态深度、收集位置、去重维度

三道题刷下来，我发现它们的差异可以浓缩成三个关键词：状态深度、收集位置、去重维度。把这三条线拉出来对比，比孤立刷十道题都管用。

5.1 结构化对比

这里面最能体现差异的是收集位置。93题在“满足边界条件”的某个中间节点收集，所以终止条件和收集绑定；78和90在每个节点都收集，所以收集代码放在递归开头。很多人刷完这几题后还是会把三份代码搞混，本质上是没有意识到这三种题对应的“树节点含义”不同。

5.2 用调试日志“看”回溯树

回溯题写的对不对，光靠人脑推演小例子可以，推到五六个元素就有点吃力了。而我推荐的办法是打印递归日志，用缩进代表递归深度，把每次进入递归的startIndex、当前path以及最终收集到的结果都打印出来。

比如在78题里，我习惯加一个这样的临时打印：

cout << string(depth * 2, ' ') << "enter: " << startIndex << " path: "; printPath(path);

运行一次，你会看到一整棵树，每个节点出现一次，保证每个节点都被收集，不再有遗漏。这个方法在90题去重时更宝贵——你可以清楚看到哪些分支被continue跳过，判断去重逻辑是不是作用在了树层而不是树枝上。我发现很多人在被问“你这个continue是树层还是树枝”时支支吾吾，就是因为从来没亲眼看过程序的递归走向。打印一轮，全部一目了然。

5.3 这三个坑我建议你亲手踩一次

复盘过程中我又把常见错误整理了一遍，每一个我都建议在本地故意写错一次再改对，印象会深得多。

第一个坑是93题的erase位置。插点后递归完忘记erase，字符串越积越长，或者erase时传参写成i而不是i+1，都会导致点号位置错乱。调试时打印每一步的字符串能快速定位。

第二个坑是78题的收集位置。把result.push_back(path)放在终止条件if里，结果漏掉中间节点。这个错误输出结果非常有迷惑性，因为只少了几行子集，不容易一眼看出问题，必须要自己手推对比。

第三个坑是90题的used判断写反。把used[i - 1] == false写成used[i - 1] == true，等于把树层去重改成了树枝去重。跑[1,1,2]会发现结果里出现两个[1]、两个[2]，去重完全失败。这个错误我第一次刷的时候也踩过，当时还以为是排序问题，后来打印日志才发现是去重维度搞反了。

6. 子集之外：从回溯到状压枚举与“第K大子集和”

刷完78和90之后，如果你觉得子集就是回溯的专属领域，那就把视野装小了。子集问题在算法里是个极其基础的模型，延伸到工程和竞赛中还有大量变体，Day21的热搜词里那几个延伸点基本都绕不开子集。

6.1 为什么工程里总要枚举子集

一个很典型的工程场景是特征选择。比如在工业传感器数据里，采集通道可能有几百路，建模前要挑出一组最有效的信号组合。这本质上就是一个枚举子集的过程——在n个特征中尝试所有可能的选择组合，找一个最优子集。之前看到过NASA公开的N-CMAPSS发动机退化数据集，里面就包含大量传感器通道，做预测性维护建模时，很多人都会用到枚举子集或者基于子集的特征筛选方法。这种场景下，回溯枚举就是最朴素的“暴力基准”。

第K大子集和是另一个常见进阶题：给定一个数组，求所有子集和按从大到小排第K个的和。常规做法是把数组拆成两半，分别枚举两个半区各自的全部子集和，排序后用双指针或二分去合并；也可以用优先队列做“贪心生成”。这些做法的基础都是“先能把子集完整枚举出来”，只是在回溯之外换了更高效的组织方式。理解了78题的子集树，再去看这些变体，会发现底层的枚举逻辑完全一致。

6.2 位运算枚举子集：另一种优雅的暴力

当数组长度n比较小（比如n <= 20）时，位运算是枚举子集最简单的武器。用二进制数的每一位代表原数组中的一个元素是否被选中，1表示选，0表示不选，那么从0到(1 << n) - 1的所有整数，就代表了全部2^n个子集。

for (int mask = 0; mask < (1 << n); mask++) { // mask 的二进制表示就是一个子集 }

如果还要按顺序枚举某个mask的子集，标准写法是：

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

这段代码每次把sub最右边的1变0，同时保留其他与mask重叠的位，能无损地遍历mask的全部非空子集。这种技巧在状压DP里特别常用，Day21热词里那个“状压dp+++枚举子集”指的就是这类操作。回溯、位运算、状压DP，三者在子集问题上其实是同一种思想的不同实现方式。回溯适合n稍大且需要剪枝的场景，位运算适合n小且追求极致简洁的场景，状压DP则在此基础上叠加状态转移，处理更复杂的优化问题。

我个人的体会是：把78和90刷透之后，后面再遇到子集相关的变体题，几乎都是在基础上加一个特性——要么加约束条件，要么换一种枚举顺序，要么引入状态压缩。底层那棵子集树没有变过。

最后说点刷题之外的东西。Day21这套题组合，真正的价值不在于让你会写三道题，而在于强迫你理解回溯的几个关键决策点：状态变量怎么设计、结果在哪里收集、重复值在哪一层去重。把这三点吃透，你后面做排列、棋盘、岛屿类问题都会轻松很多。我在刷完三题之后重新翻了一遍前几天的组合题，发现原来很多困惑其实是“收集位置”和“去重维度”没想清楚。建议你也试试这样一个动作：把Day21的三题和之前的组合题编号写在一张纸上，标注每题的状态变量、收集位置、去重维度，然后你会发现整个回溯专题的骨架就自动浮出水面了。