Day21回溯算法专题做到第三篇。前两篇我们已经把组合类问题的套路磨得很熟了——从最基本的77题组合开始到组合总和I/II再到电话号码的字母组合backtracking函数的骨架已经刻进肌肉记忆了。但到了part03难度开始上一个真正的台阶这一篇的核心不再是组合而是子集和分割两个新场景。说实在的我从组合跳到子集问题的时候第一反应是这俩不是一回事吗。但真动手写代码才发现子集问题和组合问题的思维模型有本质区别——组合关注的是选满k个就收手子集关注的是每个节点都要记录而分割问题更是把选择彻底抽象成了切割线的位置。这篇文章就把part03里最核心的几道题串起来讲清楚三个场景各自的门道以及它们背后是怎么共用同一套回溯模板的。1. 子集问题从收集叶子到收集每个节点的思维切换子集问题在LeetCode上对应的是78题题目描述很简单给一个不包含重复元素的整数数组返回所有可能的子集。比如[1,2,3]要输出[[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]。如果你已经写过组合总和那一系列题目第一眼看上去会觉得子集和组合的代码几乎一样都在递归里用startIndex控制下一层起点都是选了当前元素然后往深层走。但有一个极其关键的差异——收集结果的位置。组合问题的经典写法是void backtracking(vectorint candidates, int target, int sum, int startIndex) { if (sum target) { result.push_back(path); return; } // ... for 循环选择 }只有在满足终止条件时才把path塞进result。说白了组合问题的结果是收集树的叶子节点中间过程产生的所有中间状态都不是最终答案。子集问题恰恰相反整棵树的每一个节点不管深度多少不管下面还会不会继续递归都是合法子集。所以收集动作必须放在进入递归前的代码里且不能放在终止条件之后被return挡住。class Solution { private: vectorvectorint result; vectorint path; void backtracking(vectorint nums, int startIndex) { result.push_back(path); // 每个节点都收集 if (startIndex nums.size()) { return; } for (int i startIndex; i nums.size(); i) { path.push_back(nums[i]); backtracking(nums, i 1); path.pop_back(); } } public: vectorvectorint subsets(vectorint nums) { backtracking(nums, 0); return result; } };这段代码里最容易写错的点就是把这行result.push_back(path);放到if (startIndex nums.size())里面。如果放进去结果会是当递归走到startIndex越过数组末尾时才记录一次path——那样收集到的就只是完整走到最后的路径中间那些诸如[1]、[2]这种浅层子集全都会丢。还有个细节值得说一下这里递归函数没有显式的剪枝操作因为子集问题需要遍历所有分支剪枝反而会漏答案。这一点和组合总和那道题里sum target就return的思路完全不同新手最容易惯性代入组合题的剪枝逻辑。从复杂度上算一下nums长度为n时子集总数是2^n每个子集复制进result的成本是O(n)所以总时间复杂度是O(n * 2^n)空间复杂度O(n)主要花在递归栈上。这也是回溯类题目里典型的两倍增长复杂度看到2^n心里要有个谱。实际刷题经验告诉我第一次做子集题与其硬背模板不如在纸上把这棵递归树画出来。[1,2,3]的整棵树画一遍你就知道为什么收集语句必须在递归之前了——因为每个有path值的状态都是答案。2. 去重的真正难点树层去重与树枝去重为什么不能混为一谈子集问题做完基础版紧跟着就是90题子集II输入数组变成可能包含重复元素。比如[1,2,2]你要输出的结果不能含有重复子集。这题本质考察的是回溯中的去重逻辑和组合总和II里那套去重思路一脉相承但因为它套在子集问题上又容易让人掉进另一个坑。先说结论需要在同一层同一轮for循环内跳过重复元素这就是树层去重。实现上两种主流写法写法一用used数组记录状态class Solution { private: vectorvectorint result; vectorint path; void backtracking(vectorint nums, int startIndex, vectorbool 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; } used[i] true; path.push_back(nums[i]); backtracking(nums, i 1, used); path.pop_back(); used[i] false; } } public: vectorvectorint subsetsWithDup(vectorint nums) { sort(nums.begin(), nums.end()); vectorbool used(nums.size(), false); backtracking(nums, 0, used); return result; } };写法二直接用startIndex跳过void backtracking(vectorint 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(); } }先说一个很多人忽略的前提不管用哪种写法第一步必须先排序。used数组去重的核心是依赖相邻相等的检测不排序的话相等的元素在数组里不相邻nums[i] nums[i-1]根本判断不到。这是90题和40题里最容易踩的暗坑。再说说used[i - 1] false这个条件到底是什么意思很多博客讲到这里都含糊其辞。我换个理解方式在一个分支的递归深度上纵向如果used[i-1] true说明当前正在这个元素的分支内部继续扩展这是正常的、允许的。比如数组[1,2,2]先选了第一个2然后递归进入第二个2此时前一个2的used为true路径[2,2]是合法子集不能跳过。如果used[i - 1] false说明前一个相同的元素刚在上一层被撤销了选择而当前这层又遇到了同样的值。这代表两个路径在处理同一层时元素值相同继续走就会和上一次for循环的结果完全重复所以直接跳过。我在part02做组合总和II时也用过这个used数组但当时只记住了遇到相同就continue没理解深层的横向/纵向区别结果一到子集II这种需要每一层都收集结果的场景就懵了。这里我推荐一个调试方法在backtracking函数里把used数组当前状态和startIndex打印出来配合i的值逐层看很快就能看出什么时候used[i-1]为false什么时候为true。肉眼看得见比空想要清楚得多。回到两种写法的取舍上。写法二用i startIndex是我个人现在更常用的因为它不需要额外维护used数组代码更短但它的理解门槛稍微高一点——你必须透彻地知道i startIndex意味着在同一层循环里已经处理过这个值了这本质上就是树层去重。写法一更直白配合used[i-1] false这个条件可以做到和写法二完全相同的效果但它需要你给backtracking函数多传一个参数。刷题阶段我建议先把写法一练熟面试手撕的时候用写法二会显得更干净。这里有个重要的区别要提醒两个写法在同一个位置的具体行为上并不完全等价。比如数组[1,2,2]写法一是基于全数组全局的used状态去判断而写法二是基于当前for循环的起点去判断。大多数情况下二者结果一样但如果你的递归里还有其他进出栈的不对称逻辑可能会导致细节差异。稳妥起见如果你已经能熟练理解used数组就一直用used数组理解不了就一直用i startIndex别两种混着写混着写最容易出bug。3. 分割问题的本质把切割线当成组合中的选择节点如果说子集问题是在组合的模板上换了个收集时机那分割问题就是把组合问题的抽象方式整个换了一遍——这也是part03里我认为思维跨度最大的一步。典型题目是131题分割回文串给定一个字符串返回所有可能的分割方案要求每个子串都是回文串。比如aab结果要是[[a,a,b],[aa,b]]。我第一次看到这题陷入了困惑前面刷的组合题都是在一个一维数组上做选择这题给的是一个字符串怎么选选的是什么答案是你选的不是字符而是切割点的位置。在字符串中切割点的位置本质上与组合中startIndex之后选哪个元素是一样的——每一层递归startIndex就是上一刀切完之后的起点而for循环里i的每一次迭代就代表在i这个位置切下一刀。代码长这样class Solution { private: vectorvectorstring result; vectorstring path; bool isPalindrome(const string s, int start, int end) { while (start end) { if (s[start] ! s[end]) return false; start; end--; } return true; } void backtracking(const string s, int startIndex) { if (startIndex s.size()) { result.push_back(path); return; } for (int i startIndex; i s.size(); i) { if (isPalindrome(s, startIndex, i)) { string str s.substr(startIndex, i - startIndex 1); path.push_back(str); backtracking(s, i 1); path.pop_back(); } } } public: vectorvectorstring partition(string s) { backtracking(s, 0); return result; } };这里最值得琢磨的是if (isPalindrome(s, startIndex, i))这个判断放的位置。它不是在终止条件里做校验而是在进入下一层递归之前就做准入检查。这和组合问题里不满足条件就不选的逻辑一样——组合里可以提前判断sum是否超过target分割里则是提前判断当前准备切的这段子串是不是回文。如果不做这个判断硬把所有切法都试一遍到叶子节点才统一检查那递归树的规模会急剧膨胀做aab这种小字符串不明显但字符串一长性能差距立刻爆发出来。用生活化的类比来说startIndex就是你手上的刀下一次要落下的位置i是你这次打算切到的位置。一次切割得到一段字符串然后递归的下一层从i1重新开始。整个递归树展示的其实是所有可能的切法组合。我实际测试下来这种先判断再递归的剪枝方式在处理长回文串时比全切出来再做判断快非常多。比如对aaaaa...这种全是同一个字符的极端例子剪枝与否差距是指数级别的。我还试过把isPalindrome改成在递归外部预先算出一个布尔矩阵dp[i][j]表示s[i..j]是否回文然后用O(1)查表代替双指针判断。对超长字符串测试场景确实有优化效果但代码复杂度上去了不太利于面试时快速讲清楚日常刷题或面试用双指针的isPalindrome就够了。4. 复原IP地址多个前置校验叠加在回溯框架上分割问题里还有一道比分割回文串更综合的题93题复原IP地址。给定一个只含数字的字符串比如25525511135还原出所有合法的IP地址组合。这道题也是用backtracking做切割但相比分割回文串多了三个客观条件的约束第一IP地址必须恰好四段第二每一段必须是一个合法的数字0~255之间且不能有前导零第三每一段不能为空。三个约束叠加就特别考验你把判断条件嵌进递归框架的能力。核心实现如下class Solution { private: vectorstring result; 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] 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)) { s.insert(s.begin() i 1, .); pointNum 1; backtracking(s, i 2, pointNum); pointNum - 1; s.erase(s.begin() i 1); } } } public: vectorstring restoreIpAddresses(string s) { if (s.size() 4 || s.size() 12) return result; backtracking(s, 0, 0); return result; } };这道题有至少四个细节值得单独拿出来讲。第一终止条件的设定。这里用pointNum 3而不是startIndex s.size()作为递归出口。因为IP地址恰好四段只要插了三个点就已经把字符串分成四段了。剩下要做的事情就只剩一件事验证最后一段是否合法。这个设计比切完所有字符再检查要优雅得多也省去了很多无效递归。第二字符串的增删操作。insert和erase是std::string里的操作时间复杂度O(n)但因为字符串长度最多也就12个字符这个成本可以忽略不计。需要注意的是插入一个点之后下一次递归的起点从i1变成了i2——因为要跳过.这个字符。这里特别容易写错成i1一错就会反复检查到插入的句点。第三for循环里的合法性判断剪枝。如果s[startIndex..i]这一段本身就不是有效数字比如超过了255那就不用再往i后面试了。注意这个地方可以加个小优化如果剩余字符数量比需要的还多可以直接break或continue因为当前段已经不可能划分出合法IP了。第四主函数里的一行防御代码if (s.size() 4 || s.size() 12) return result;。字符串长度小于4不可能分成四段大于12则必然有一段超过三位数。这个前置判断在LeetCode上能帮你省掉一大拨边界用例的递归开销属于典型的入口处先堵住明显不合法输入的思路。我在刷这道题时踩过的最蠢的坑是忘了判断前导零。比如010010这种字符串0.10.0.10算不算合法其实每一段的0是合法的单独的0但01之类的前导零就不合法。我一开始的isValid只判断了数字是否大于255结果把01.0.0.1这种也当成了合法IP直接提交就是Wrong Answer。所以判断前导零的逻辑必须单独写if (s[start] 0 start ! end) return false;——意思是只有长度大于1且以0开头的段才非法单独一段0完全合法。5. 回溯part01到part03的一条主线模式识别的方法论做完part03这三类题之后我最大的感受是回溯算法看似每个题的代码都差不多但真正区分难度的是你能不能快速识别出这道题到底属于哪一种抽象模型。我到part03才算把这条主线理顺了。先放一个我从三天题目里总结出来的对照表问题类型抽象选择的对象终止条件结果收集位置典型题目组合从一组数里选k个path.size() k叶子节点77, 216, 39, 40子集从一组数里选任意个startIndex越界每个节点78, 90分割在一维结构上选切割点startIndex走到末尾叶子节点131, 93这张表不是死记硬背用的而是当你拿到一道新题时用来做模式匹配的。拿到题目先做三连问答案是不是若干个元素的组合如果是看有没有数量限制有就套组合模板。答案是不是所有子集/所有不重复组合如果是把收集语句提到递归之前。答案是不是把一个字符串/序列划分成若干合法片段如果是把for循环里的i理解成切割点用startIndex表示上一次切割结束的位置。这套方法论其实是从代码随想录回溯专题的编排思路里延伸出来的part01打基础组合、组合总和part02练细节去重、剪枝part03就是逼你把抽象模型灵活切换。子集问题的收集所有节点和分割问题的把切割点当作选择本质都是对同一棵递归树的不同解读方式。还有一点值得反复体会回溯算法写的次数多了你会发现模板本身几乎不变变的是三样东西——result里最终装的是什么、path里累积的是什么、以及每次递归的终止条件是什么。如果你能做到看到一个题就快速把这三点分别说出来回溯类题目就基本通关了。我这几天的实际经验是不要着急多刷题每做完一道题就打开代码用荧光笔在纸上标出收集位置剪枝位置终止条件这三处对比不同题目之间的差异。等积累到五六个题之后你会发现原本模糊的模式识别能力会变得非常清晰。Day21的part03说到底练的不只是三道题的解法而是建立这种看题先归类的思维习惯。