企业官网建设流程全解析

1. 回溯第三关：从组合到排列的过渡地带

训练营打卡进入第二十四天，今天这组题很有意思——93.复原IP地址、78.子集、90.子集II，三道题放在一起，恰好构成回溯算法从“组合问题”向“子集问题”过渡的完整阶梯。如果你已经跟完了前几天的组合问题（77.组合、216.组合总和III、17.电话号码的字母组合、39.组合总和、40.组合总和II），会发现今天的题其实是在同一套回溯框架上做了两处关键变形：一是把“在数组里选元素”改成“在字符串上切段”；二是把“收集叶子节点”改成“收集所有节点”。

先说结论，方便你评估今天这组题的难度梯度。93题是回溯里比较考验细节的题目，因为它不仅是选数，还牵扯到字符串的切分和合法性判断，稍不注意就会出现前导零、越界这类隐蔽bug。78和90这两道子集题反而简单很多，核心就一个坑——收集结果的时机，搞懂了子集的求解逻辑，这两道题基本十分钟内能AC。不过90题涉及去重，需要先排序，这个排序动作背后的原因值得你停下来想清楚，否则换个马甲的去重题出来你还是会懵。

先聊一个观察。回溯专题学到现在，你会发现一个规律：所有回溯问题都可以套进同一个模子里。这个模子长这样：

void backtracking(参数) { if (终止条件) { 存放结果; return; } for (选择本层集合中的元素) { 处理节点; backtracking(路径, 新参数); 回溯，撤销处理结果; } }

套路就是这么个套路，但难点在于每道题都有两个“私人定制”的部分：终止条件怎么写，以及for循环里的处理操作是什么。今天的93题就是典型例子——它的终止条件和处理操作都跟字符串操作强绑定，不是在vector里push/pop，而是在字符串上插点、删点、判断合法。这也是为什么我说93题值得认真做一遍，做完这道题，你对“回溯的每一步到底在做什么”的理解会明显上一个台阶。

1.1 三道题为什么放在同一天

代码随想录把这三道题放在一天，不是随手排的。从左到右看，它们其实在逐步增加复杂度：

• 93题：回溯 + 字符串操作 + 多重合法性判断，考察的是你在回溯过程中能不能处理好局部状态。
• 78题：回溯的基础形态，但收集结果的位置从“叶子”变成“所有节点”，这是理解子集问题的关键一跃。
• 90题：在78的基础上叠加去重，而去重的前提是排序，排序会改变元素顺序，但子集不关心顺序（因为本质是选下标组合），所以排序在这里是无害的。

所以今天的学习主线是：先通过93题强化回溯的“动作感”，再用78题刷新对结果收集时机的认知，最后用90题搞懂同一层去重的实现原理。你按这个顺序刷，思路会非常顺。

2. 93.复原IP地址：在字符串上玩回溯

先看题目：给定一个只包含数字的字符串s，要求复原它并返回所有可能的IP地址格式。所谓有效IP地址，就是四段数字，每段在0到255之间，且不能有前导零（除非这个段本身就是0）。

这是一道标准的切割问题。组合问题是“从N个数里选K个数”，切割问题其实是“从N个字符里找K个切割点”。你在纸上画一下：25525511135这个字符串，要在三个位置切三刀，切成四段，每一段都要满足IP段的约束。

2.1 终止条件不是“切完”，而是“切了三刀”

很多第一次做这道题的同学，会把终止条件写成“startIndex走到字符串末尾”。但仔细想想就会发现问题：如果只以“走完”作为终止，那么切两刀、切五刀的情况也会被算进来，但IP地址必须有四段。所以93题里终止条件要跟段数绑定——当逗点数量等于3时，只需判断最后一段是否合法，合法就收入结果。

我用的是代码随想录的标准思路，在原始字符串上操作，用一个pointNum记录已插入的逗点数量：

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)) { s.insert(s.begin() + i + 1, '.'); pointNum++; backtracking(s, i + 2, pointNum); pointNum--; s.erase(s.begin() + i + 1); } else { break; // 这一段已经不合法，后面的更不合法，直接剪枝 } } }

这里有个细节容易看懵：s.insert(s.begin() + i + 1, '.')为什么是i + 1？因为当前段是从startIndex到i，你要在i后面插入逗点。而插入之后，下一段的起始位置就变成了i + 2，因为跳过了刚插入的那个点。

2.2 合法性判断的三个细节

isValid函数是这道题最容易出bug的地方，一共三个判断条件，少了任何一个都会挂：

bool isValid(const string& s, int start, int end) { if (start > end) return false; // 前导零判断：长度大于1且第一位是0，就非法 if (s[start] == '0' && start != end) 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; // 超过255 } return true; }

第一个条件检查前导零。注意s[start] == '0' && start != end这种写法：如果这一段的开头是0，但这段长度大于1，比如“01”，那直接就是非法段。但如果段本身就是“0”，也就是start == end，那是合法的，比如IP地址255.255.255.0最后的0。

第二个条件检查非数字字符，这道题的输入都是数字字符，所以这个判断看起来是“防御性”的，但养成写全的习惯没坏处。

第三个条件是累加判断是否超过255。很多人会写成“先算出整个数字再判断”，但那样有溢出风险——如果一段是“999999999999”，转成int直接爆了。边累加边判断，一旦超过255立即返回，既安全又省事。这也是我建议大家写num = num * 10 + (s[i] - '0'); if (num > 255) return false;的原因。

提示：从“这一段已经不合法就break”这个剪枝也能看出，同一个循环内，i越大意味着数字位越多，数值越大，所以一旦当前长度已经不合法，后面的组合只会更大，直接跳出循环即可。这个剪枝思路在组合总和II里也出现过，你已经掌握过了。

2.3 剪枝优化：提前排除不可能的情况

我之前漏掉了一个前置剪枝：如果传入的字符串s长度小于4或者大于12，直接返回空结果。因为IP地址最少4个字符（0.0.0.0），最多12个字符（255.255.255.255）。这个判断放在主函数里，能避免无效递归：

vector<string> restoreIpAddresses(string s) { result.clear(); if (s.size() < 4 || s.size() > 12) return result; backtracking(s, 0, 0); return result; }

这算是“先全局排除再进入局部递归”的思路。你可能会觉得一个4到12的长度判断省不了多少事，但我在实际测试中发现，当输入是“0000000000000000”这种超长字符串时，没有这个前置判断，递归会白白跑一大圈才被合法性判断拦住。加了它就一步到位。

2.4 93题的常见错误清单

做这道题时我反复踩过的坑，整理成一张排查表给你：

3. 78.子集：在树的每一个节点上收集结果

再看第二题。题目：给你一个整数数组nums，数组中的元素互不相同，返回该数组所有可能的子集。解集不能包含重复的子集。

这道题是回溯里“最不像回溯”的一道，因为它的终止条件看起来根本不存在。你先感受一下代码有多短：

vector<vector<int>> result; vector<int> path; void backtracking(vector<int>& nums, int startIndex) { result.push_back(path); // 收集子集，要放在终止条件的上面 if (startIndex >= nums.size()) { // 其实这个条件可以不加，for循环会自己结束 return; } for (int i = startIndex; i < nums.size(); i++) { path.push_back(nums[i]); backtracking(nums, i + 1); path.pop_back(); } }

核心就一个地方：result.push_back(path)写在了进入递归的最前面。这意味着什么？意味着每个节点被访问到时，当时的path都会被记录为一个子集。

3.1 为什么子集要在每个节点收集结果

回顾一下之前做组合题时，代码长什么样：

if (path.size() == k) { // 终止条件到达叶子 result.push_back(path); return; }

组合题只在叶子节点收集，因为组合问题要求“取满K个数”。而子集问题没有长度要求，从空集开始，中间任何一个状态都是合法子集。子集问题求的本质上就是整棵树的所有节点，而不是叶子到根路径上的特定节点。

你可以把回溯的过程想象成一次深度优先遍历：从根出发，每走一步就往path里加一个元素，每到达一个新节点，这个节点代表的集合就是一个子集。空集是根节点本身，所以当你第一次进入backtracking时，path还是空的，这时候就收集到了空集。

这也是为什么子集的代码里其实不需要显式写终止条件——因为for循环遍历完所有元素时，函数自然返回。但是为了跟回溯模板保持一致，也为了后面做更复杂的子集变形题时逻辑清晰，很多人还是会写上。我自己写的时候会写上，这是个人习惯，不写也不会错，但写了之后递归结构更完整，出问题更容易排查。

3.2 子集问题的时间复杂度

简单算一下：数组长度为n，每个元素都有“选”和“不选”两种状态，所以子集总数是2^n。每个子集的平均长度是n/2，最终构造结果的复杂度大约是O(n·2^n)。这个复杂度在回溯题里属于“注定没法优化”的类型，因为答案本身就有这么多。

不过很多同学纠结的不是复杂度，而是一个直观问题：“为什么我的结果顺序跟标准答案不一样？”这其实是正常的。子集的结果顺序取决于递归的遍历顺序，不同的遍历方式会产生不同的排列顺序，但只要解集不重不漏，就是对的。比如在LeetCode上，答案的排列顺序和你的不一样，只要每个子集都出现且没重复，依然可以通过。

3.3 78题的一个关键认知

做子集题之前，先想清楚一件事：子集问题跟“组合”和“排列”的区别本质上是顺序敏感性。组合问题（如[1,2,3]取2个）和子集问题都只关注哪些元素被选中，不关注顺序，所以都用startIndex来控制不回头。而排列问题每次都要从头开始选，所以用used数组标记已使用的元素，不需要startIndex。

一旦你把“组合”和“子集”的关系想通，78题就变成了一道模板题。你甚至可以把78题的解法直接套到组合问题里——只要把收集结果从“节点”改为“叶子”，就得到了标准的组合题代码。

4. 90.子集II：去重问题的标准解法

第三题，也是今天稍有分量的一道。题目给你一个整数数组nums，可能包含重复元素，返回所有可能的子集（幂集）。解集不能包含重复的子集。

示例：nums = [1,2,2]，输出应为[[], [1], [1,2], [1,2,2], [2], [2,2]]。这里[1,2]只能出现一次，不能因为两个2位置不同就生成两个[1,2]。

4.1 为什么必须先排序

90题的解法核心就是一句话：先排序，然后在同一层内跳过重复元素。

排序的目的是把相同的元素聚在一起，这样去重的时候才能通过“和前一个元素比较”来判定重复。如果不排序，那么两个2一个在索引1一个在索引3，你遍历的时候nums[i] == nums[i-1]这种比较就失效了，因为你不知道前面是否出现过相同元素。

这里需要区分一个概念：树枝去重 vs 树层去重。举个例子，在[1,2,2]这个数组中，如果第一个分支选的是第一个2，第二个分支选的是第二个2，那么这两个分支产生的子集是重复的，这就是“同一层”上的重复，必须去重。但是如果你在一条分支里先后选了两个2，那产生的子集是[2,2]，这是合法的子集，不能被去掉。所以“树层去重”不等于“树枝去重”，很多人就在这里栽跟头。

4.2 两种去重写法，本质相同

第一种写法是用一个used数组标记元素是否被使用过，这是代码随想录的标准解法：

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++) { // used[i - 1] == false，说明同一树层nums[i - 1]已经使用过， // 现在nums[i]与nums[i-1]相同，必须要跳过 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(); } }

第二种写法不用used数组，直接通过startIndex比较前后元素：

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(); }

两种写法效果一样，区别在于判定逻辑的表述角度不同。第一种写法的判定条件是“前一个相同元素已经被使用过但被回溯还原成了false”，说明它在同一层的另外一个分支里出现过；第二种写法更直接——i > startIndex意味着这不是本层第一个被尝试的元素，而当前元素和上一个元素相等，说明上一个元素在本层已经被处理过，这次再选它就是重复的开始。

我个人的使用习惯是：如果题目本身用到used数组（比如全排列问题），就统一用第一种写法；如果只是子集去重，就直接用startIndex判断，代码更简洁。

注意：没有排序，以上两种写法全部失效。所以“先排序”是不可省略的前置步骤。这跟组合总和II的去重逻辑一模一样，如果你之前已经掌握了40题，这里就是纯复习。

4.3 去重的底层原理：回溯树上的“同层跳过”

用具体例子走一遍，你就能彻底明白“树层去重”是啥意思。

以nums = [1,2,2]为例，排序后是[1,2,2]，下标0的值是1，下标1和2的值都是2。

• 第一层：取1，进入递归，先生成[1]，再往下生成[1,2]、[1,2,2]。
• 第一层再取下标1的2，进入递归，生成[2]、[2,2]。
• 第一层继续取下标2的2，此时i > startIndex && nums[i] == nums[i-1]成立（因为i=2，startIndex=0，且两个2相等），直接跳过。

走到这里，你会发现如果没跳过下标2的2，会再生成一遍[2]和[2,2]，完全重复。所以这个continue的作用，是保证同一层循环中，值相同的元素只被处理一次。而“同一层”这个表述对应的就是for循环内的迭代——每一层for循环，代表的是回溯树中同一深度的不同分支。

至于为什么树枝不去重，也就是为什么在递归到[1,2]之后还能再取第二个2形成[1,2,2]，是因为第二次取2发生在下一层递归里，这时i不再等于startIndex的同一个值，判定条件i > startIndex && nums[i] == nums[i-1]的结果变了。你可以自己画一遍这棵树，印象会非常深。

4.4 90题的时间复杂度

因为去重要先排序，排序复杂度是O(n log n)。回溯本身仍然是O(n·2^n)（最坏情况，比如所有元素都不重复时）。所以总复杂度是O(n log n + n·2^n)，在大O意义下就是O(n·2^n)。

5. 三道题横向对比与调试心得

最后把三道题放在一起做个横向对比，你复习的时候看这张表就够了：

5.1 三道题最容易混淆的两个点

第一个容易混淆的是93题的终止条件跟其他回溯题不一样。大多数回溯题的终止条件是“路径长度达到K”或“startIndex走完”，但93题是用“插了点”来约束状态，因为IP地址的段数是固定的4段，而每段的长度是可变的。这其实是回溯里“用额外计数变量做终止条件”的典型例子，类似的还有N皇后问题用row来控制行数。

第二个容易混淆的是78题的收集位置。如果你把result.push_back(path)放到if (startIndex >= size)的后面（也就是叶子节点才收集），那你会得到一个只包含完整子集的错误答案——[1,2]这种中间状态全部丢失。子集的收集一定要放在递归进入的最前面。你可以把这段代码的执行过程在纸上推演一遍：进入函数，先收集当前path代表的子集，然后尝试下一个元素，再进入更深层递归。这样就保证了从空集到每个中间状态都被记录。

5.2 现场调试经验：三步定位bug

训练营打卡这段时间，我总结出一个回溯题的调试三板斧，今天这组题尤其适用：

第一步，打印每个节点的path和startIndex。不要急着看结果对不对，先看递归的走向是否符合预期。直接在backtracking函数第一行加一句：

cout << "path: ["; for (int x : path) cout << x << " "; cout << "] startIndex=" << startIndex << endl;

第二步，小规模数据手工推演。凡遇到回溯题，先用一个只有3个元素的输入跑一遍，把递归树在纸上画出来。比如90题用[1,2,2]，画完你就知道哪个分支被continue拦住了，为什么拦的是那一层。

第三步，对比错误结果，判断是“多解”还是“少解”。结果里出现了[1,2]和另一个[1,2]，说明去重失败，是树层没去重；结果里缺了[2,2]，说明你把树枝也去重了，递归深处的相同元素被误判成重复了。

5.3 今天这组题的实际做题节奏

如果你是从零开始刷这三道题，我的建议是控制在90分钟以内。93题花45分钟，因为它的细节多；78题花15分钟，因为它就是开窍题；90题花30分钟，因为去重逻辑需要你多想一层。

做题的时候，先别急着看题解，拿着回溯模板试着填空：终止条件怎么写？for循环里处理什么？怎么收集结果？填完再对照题解，你会发现大部分卡点其实就卡在那一两个填空上。

训练营到这个阶段，你应该已经形成一种“肌肉记忆”了——看到回溯题先想三件事：能不能排序、收集时机是节点还是叶子、要不要去重。把这三个问题想明白，再难的题也能拆出个七八分。今天的93题就在“能不能排序”上给了个反例：字符串切分问题不能排序，因为顺序是题目给定的。而90题恰好反过来，必须先排序才能解题。同样是回溯，一个不能排序一个必须排序，这个反差值得你记住。