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。这个判断放在主函数里能避免无效递归vectorstring 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题的常见错误清单做这道题时我反复踩过的坑整理成一张排查表给你错误类型错误原因正确做法终止条件写成startIndex size没有限制段数导致切了两段、五段也进结果集用pointNum 3控制判断最后一段递归传参写成i1忘了中间隔了一个刚插入的逗点插入点后下一段起点是i2前导零判断遗漏把“01.1.1.1”当合法段段长大于1且第一位是0时必须return false不在循环里break无效段还继续尝试更长段浪费时间当前段非法则break同层剪枝3. 78.子集在树的每一个节点上收集结果再看第二题。题目给你一个整数数组nums数组中的元素互不相同返回该数组所有可能的子集。解集不能包含重复的子集。这道题是回溯里“最不像回溯”的一道因为它的终止条件看起来根本不存在。你先感受一下代码有多短vectorvectorint result; vectorint path; void backtracking(vectorint 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数组标记元素是否被使用过这是代码随想录的标准解法vectorvectorint result; vectorint path; void backtracking(vectorint nums, int startIndex, vectorbool 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]成立因为i2startIndex0且两个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. 三道题横向对比与调试心得最后把三道题放在一起做个横向对比你复习的时候看这张表就够了维度93. 复原IP地址78. 子集90. 子集II数据载体字符串数组无重复数组有重复递归参数startIndex pointNum只startIndex只startIndex终止条件pointNum 3判断最后一段可不写可不写收集结果时机叶子节点所有节点所有节点核心特殊操作插入/删除逗点、合法性判断无先排序同层去重去重方式无每段取值合法即唯一无used数组 或 startIndex跳过时间复杂度O(3^4)常数级O(n·2^n)O(n·2^n)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题恰好反过来必须先排序才能解题。同样是回溯一个不能排序一个必须排序这个反差值得你记住。