代码随想录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: vectorstring 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: vectorstring 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”和“写了i1而不是i2”这两个点我在本地调试时各踩过一次写代码时盯紧就行。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(vectorint 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: 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; } path.push_back(nums[i]); used[i] true; backtracking(nums, i 1, used); used[i] false; path.pop_back(); } } public: vectorvectorint subsetsWithDup(vectorint nums) { sort(nums.begin(), nums.end()); vectorbool used(nums.size(), false); backtracking(nums, 0, used); return result; } };如果你用i startIndex版本可以去掉used数组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(); } }我个人在比赛和面试中更喜欢用i startIndex版本因为它不需要额外维护一个数组代码短也不容易在递归里忘记重置used状态。但如果你正在跟代码随想录我还是建议把used数组版本彻底弄懂因为后面很多回溯题都会用这个套路提前打好基础不吃亏。5. 三题放一起的复盘状态深度、收集位置、去重维度三道题刷下来我发现它们的差异可以浓缩成三个关键词状态深度、收集位置、去重维度。把这三条线拉出来对比比孤立刷十道题都管用。5.1 结构化对比题目问题类型核心状态变量终止条件收集结果位置去重方式93.复原IP地址切割startIndex pointNumpointNum 3切割完且第四段合法时无重复但需合法性剪枝78.子集子集startIndex隐式终止每次进入递归立刻收集无需去重90.子集II子集含重复startIndex used隐式终止每次进入递归立刻收集排序 树层去重这里面最能体现差异的是收集位置。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而不是i1都会导致点号位置错乱。调试时打印每一步的字符串能快速定位。第二个坑是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的三题和之前的组合题编号写在一张纸上标注每题的状态变量、收集位置、去重维度然后你会发现整个回溯专题的骨架就自动浮出水面了。