回溯算法大概是面试里最容易“一看就会一写就废”的题型。我刷到代码随想录 Day21 的时候三道题连排93 复原 IP 地址、78 子集、90 子集 II正好把回溯的三种经典场景全占了——字符串切割、全量枚举、重复元素去重。这篇文章不打算把模板背一遍就完事而是用三道题把“为什么这么写”彻底讲透看完你能直接照着重写一遍顺便把递归树打印的调试方法也学会。适合正在打基础刷题的人也适合准备面试想快速捡起回溯的朋友。好开始。1. 回溯问题的整体思路与三道题的定位1.1 回溯算法的核心思想与套路模板回溯说白了就是一棵隐式树的深度优先遍历。你在每个节点上做选择往深处走走不通就回头换一条路再走。这个“回头”的动作就是回溯。它解决的问题都有一个共同特征需要枚举所有满足条件的组合、子集或排列。代码随想录里给的模板特别精简我加了点自己的理解变成四个要素选择列表这一层 for 循环能选哪些元素。组合类问题通常用 startIndex 控制起点排列类问题用 used 数组控制是否用过。递归调用选了当前元素之后进入下一层参数跟着变。撤销操作从当前分支返回时把刚才加进 path 的元素弹出去恢复现场。终止条件什么时候把当前 path 存进结果。组合题是长度够了切割题是分割完成子集题比较特殊每个节点都要存。模板长这样void backtrack(参数) { if (终止条件) { 存放结果; return; } for (int i startIndex; i nums.size(); i) { path.push_back(nums[i]); // 处理节点 backtrack(新的参数); // 递归下一层 path.pop_back(); // 回溯撤销本层 } }这套模板的坑点不在模板本身而在三个问题上一是终止条件写在哪、怎么写二是结果收集放在递归入口还是终止条件里面三是循环里什么时候剪枝、什么时候去重。三道题正好各覆盖一个。1.2 三道题放在一起的递进逻辑为什么把这三道题放在同一天刷因为它们的递进关系非常明显。78 子集是基础让你理解“所有节点都是答案”这件事这跟组合问题“只收集叶子节点”是完全不同的思路。90 子集 II 是在 78 的基础上加了重复元素逼着你去处理去重。93 复原 IP 地址则是把回溯从“数组里选数字”上升到“字符串上做切割”处理的是索引和边界。我当时的感觉是78 全懂了90 就只是加了个排序和一行判断90 搞定后93 就是换了个收集结果的姿势但终止条件反而更绕。所以建议你也按这个顺序刷先 78 再 90 最后 93会有种一路打通的感觉。下面一道一道说。2. 93 复原 IP 地址字符串切割的边界与终止条件2.1 题意拆解与切割思路给一个只含数字的字符串要求往里面插三个点把它分成四段每段都是合法的 IP 地址段。合法条件是每段在 0 到 255 之间且不能有前导零——除了数字 0 本身是合法的一段像“01”这种就是非法。比如“25525511135”可以切成“255.255.11.135”和“255.255.111.35”。“0000”只能切成“0.0.0.0”因为“00”是非法前导零。“101023”能切成五种这里就不全列了后面调试部分会给完整输出。这种题天然适合回溯。你每次截取 1 到 3 位数字作为下一段截完用 isValid 检查一下合法就往字符串里插个点不合法就直接 break——为什么是 break 不是 continue因为 IP 段最多三位如果当前从 startIndex 截 i 位已经超了 255那再往长截只会更大后面的分支都不用看了。2.2 递归结构与终止条件怎么定很多人在终止条件这里犯迷糊。我用的是代码随想录的写法pointNum 表示已经插了几个点。终止条件不是判断 startIndex 到了字符串末尾而是判断 pointNum 3。因为插满 3 个点后还剩最后一段需要单独截取并校验校验通过才把整个串加入结果。这里有一个隐藏边界当 pointNum 3 时必须保证 startIndex s.size()也就是说最后一段不能是空串。否则像“255255”这种字符串切成“255.255.”最后一段空会被当成合法结果加进去这就是个明显的 bug。递归函数长这样参数s会被修改插入点的字符串、startIndex本轮切割起点、pointNum已插入的点数核心循环for (int i startIndex; i s.size(); i) { if (isValid(s, startIndex, i)) { s.insert(s.begin() i 1, .); // 在 i 后面插点 pointNum; backtrack(s, i 2, pointNum); // 点是间隔符所以下一轮起点 2 pointNum--; s.erase(s.begin() i 1); // 撤销插点 } else { break; } }注意 insert 之后原来下标 i 后面多了个点所以下一次递归的 startIndex 要传 i 2而不是 i 1。这个 2 是我第一次写的时候最容易漏的点漏了就死循环或者重复截取。2.3 IP 段合法性校验为什么不能直接用 stoiisValid 函数看起来很简单但我强烈建议别偷懒用 stoi原因后面说。先看手写版本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] 9 || s[i] 0) return false; // 非数字 num num * 10 (s[i] - 0); if (num 255) return false; // 超范围 } return true; }为什么不直接用 stoi两个原因。第一如果截出来的是“25525511135”这种超长字符串stoi 会直接抛出 out_of_range 异常程序崩溃你得先截短再转麻烦。第二stoi 没办法帮你判断前导零比如“01”转出来是 1看起来合法实际 IP 段不允许。手写循环的时候只要最高位是 0 且字符串长度大于 1就一定能拦住。2.4 复原 IP 地址最容易踩的三个坑第一个坑是 insert/erase 的索引偏移。插入点之后字符的位置整体右移撤销的 erase 操作要传同一个位置。我见过有人 insert 用了 i 1erase 却传 i结果字符串越删越乱。第二个坑是终止条件里没检查剩余字符。pointNum 3 时如果 startIndex 已经等于 s.size()说明最后一段是空的直接返回不进结果。第三个坑是循环里用了 continue 而不是 break。前面说了截取长度从 1 到 3 逐渐增加。当长度为 3 时 num 已经超过 255长度为 4 只会更大所以不需要继续试探break 能省掉所有无效分支。这个剪枝虽然不改变结果但能让递归树小不少。我也试过另一种写法不用字符串插入而是用 vectorstring ips 保存四段递归结束后再把四段拼成完整的 IP。这种实现避免 insert/erase 的索引问题思路更直观性能也更好。下面给个精简版class Solution { public: vectorstring restoreIpAddresses(string s) { if (s.size() 4 || s.size() 12) return {}; vectorstring res, seg; dfs(s, 0, res, seg); return res; } void dfs(string s, int start, vectorstring res, vectorstring seg) { if (seg.size() 4) { if (start s.size()) { res.push_back(seg[0] . seg[1] . seg[2] . seg[3]); } return; } for (int len 1; len 3 start len s.size(); len) { string part s.substr(start, len); if (!isValid(part)) continue; seg.push_back(part); dfs(s, start len, res, seg); seg.pop_back(); } } };这两种写法都行个人更推荐 vector 版逻辑清楚只是拼接的时候注意别多拼点。刷题阶段如果你能两个版本都写一遍对回溯的理解会更扎实。3. 78 子集在递归入口收集所有节点3.1 子集与组合、排列的本质区别先想一个问题组合题“组合总和 III”是在什么时候收集结果的是在 k 个元素都选完也就是叶子节点的地方。而子集题不一样[1][2][1,2] 这些中间状态通通都是答案。换句话说组合问题的答案是树的叶子子集问题的答案是整棵树的全部节点。这个区别直接决定了代码里 result.push_back(path) 放在哪里。如果你的代码是先判断终止条件再收集结果那最后收集的只有叶子空集和中间子集全丢了。排列问题的区别又不一样。排列不需要 startIndex因为每个位置都能重新选其他位置的元素所以要用 used 数组标记是否用过。子集和组合都用 startIndex 保证“后面的元素不回头选”这样才不会产生 [1,2] 和 [2,1] 这种重复。3.2 完整代码与收集时机分析78 子集的完整实现class Solution { public: vectorvectorint subsets(vectorint nums) { vectorvectorint res; vectorint path; dfs(nums, 0, res, path); return res; } void dfs(vectorint nums, int startIndex, vectorvectorint res, vectorint path) { res.push_back(path); // 每个节点都是子集先收集 if (startIndex nums.size()) return; // 没有可选元素就返回 for (int i startIndex; i nums.size(); i) { path.push_back(nums[i]); dfs(nums, i 1, res, path); path.pop_back(); } } };注意第一行就是 res.push_back(path)这一步已经在收集空集了。进入递归时 path 可能是空可能是 [1]可能是 [1,2]每个状态对应一个子集全部收进结果。然后才是判断 startIndex 是否越界。其实就算不写这个终止条件也能结束因为 for 循环在 i 到达 nums.size() 时自然结束但写上更清晰也符合回溯模板的习惯。3.3 复杂度与结果顺序时间复杂度是 O(n * 2^n)。为什么乘 n因为一共 2^n 个子集每个子集都需要拷贝一份 path 到 res 里拷贝一次最坏 O(n)。空间复杂度 O(n)递归深度最多 n 层path 存储 O(n)。还有个细节输出结果的顺序。以 [1,2,3] 为例我写的递归会得到 [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]这是按“前缀深度优先”的字典序不是从小到大的字典序。LeetCode 只要求包含所有子集不比较顺序所以没问题。但如果题目要求字典序输出你就需要收集完再排序或者调整递归顺序。4. 90 子集 II排序去重的两种写法4.1 重复元素为什么会生成重复子集90 题给的是 [1,2,2]数组中两个 2 是不同的元素但对结果来说它们是不可区分的。如果你用 78 的代码直接跑会得到 [[1,2(第一个2)], [1,2(第二个2)]] 这种视觉上重复的结果。重复的根源在于在同一层递归的 for 循环里如果前面已经选过一个 2后面又遇到一个相等的 2那么从第二个 2 出发的所有分支生成的子集跟前一个 2 的分支完全一样。解决原则就一句话先排序让相等的元素相邻然后在循环里跳过“同层已经处理过的重复元素”。4.2 树层去重 vs 树枝去重这是回溯去重里最经典的概念很多人在这里绕晕。我用树来拆解。树层指的是同一个父节点下面的多个分支也就是同一个 for 循环里的多次迭代。两个相同的元素如果出现在树层那么第二个分支是第一个分支的重复必须去掉。树枝指的是从根到某个叶子的单条路径也就是递归深入的过程。路径上允许出现重复元素比如 [1,2,2]这是合法子集因为两个 2 是数组里不同位置的两个值。很多初次接触的人会把这两者搞混写去重的时候连树枝的重复也一并砍掉结果 [1,2,2] 这个正确结果就没了。记住去重只去树层不去树枝。4.3 used 数组法与 startIndex 跳过法对比代码随想录里给了两种写法我都写出来对比一下。第一种used 数组法。需要额外维护一个 used 数组标记当前递归路径上哪些元素已经用过class Solution { public: vectorvectorint res; vectorint path; vectorvectorint subsetsWithDup(vectorint nums) { sort(nums.begin(), nums.end()); vectorbool used(nums.size(), false); dfs(nums, 0, used); return res; } void dfs(vectorint nums, int startIndex, vectorbool used) { res.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; dfs(nums, i 1, used); used[i] false; path.pop_back(); } } };这里的判断逻辑是当前元素和前一个元素相等且 used[i-1] 为 false说明前一个相同元素不在当前路径上它一定是本层 for 循环中已经处理完并回溯的元素所以当前元素属于树层重复跳过。如果 used[i-1] 为 true说明前一个 2 在路径上比如 [1,2,2] 这种情况这是树枝上的合法重复保留。第二种startIndex 跳过法。不需要 used 数组直接比较下标class Solution { public: vectorvectorint res; vectorint path; vectorvectorint subsetsWithDup(vectorint nums) { sort(nums.begin(), nums.end()); dfs(nums, 0); return res; } void dfs(vectorint nums, int startIndex) { res.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]); dfs(nums, i 1); path.pop_back(); } } };关键在 if (i startIndex)而不是 if (i 0)。因为每次递归都会重置起点为 startIndex如果写成 i 0会出现把合法的树枝重复也跳过的情况。只有 i startIndex 才能精确表达“本层 for 循环里已经处理过 nums[i-1]”。两种写法我实测下来startIndex 法代码更短used 数组法更通用——排列问题必须用 used 数组。建议都掌握至少要能讲清楚为什么一个用 used[i-1]false一个用 i startIndex。4.4 去重最容易犯的错第一个错是忘记排序。去重逻辑依赖相同元素相邻不排序的话 [1,2,1] 里两个 1 不相邻判断直接失效。所以先排序这是前提不是可选项。第二个错是在循环里直接写 if (nums[i] nums[i-1]) continue而没加 i startIndex 的判断。这样会把同一枝条内部的重复也拦掉[1,2,2] 的叶子子集直接被砍掉。第三个错是结果里出现重复元素也就是根本没去重。检查方法很简单跑一下 [1,2,2]输出应该是 [[], [1], [1,2], [1,2,2], [2], [2,2]]长度是 6。如果你输出里有两个 [2]那就是去重没生效。关于这一块后面《常见问题速查表》里我会把怎么检查列全。5. 实操过程、调试技巧与常见问题速查5.1 三道题的输出对照与自测用例写题不能只看逻辑要真的跑起来。我把三道题的关键自测用例和期望输出列成表方便你对照调试。题目输入期望输出93 复原 IP 地址25525511135[255.255.11.135, 255.255.111.35]93 复原 IP 地址0000[0.0.0.0]93 复原 IP 地址101023[1.0.10.23, 1.0.102.3, 10.1.0.23, 10.10.2.3, 101.0.2.3]78 子集[1,2,3][[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]90 子集 II[1,2,2][[], [1], [1,2], [1,2,2], [2], [2,2]]这些输出我都是实际跑过验证的。特别是 101023 这个用例覆盖了“0 单独成段”和“非 0 开头”的情况非常适合回归测试。你写完代码后先用这几个用例过一遍再随机生成几个字符串测试比如“123456789”这种没有合法切分的确保结果是空数组而不是死循环。5.2 状态打印法调试回溯回溯题最怕找不着 bug。我调试这类题的固定套路是在 dfs 入口打印当前层的信息包括递归深度、startIndex、当前 path、以及关键变量。以 90 题为例void dfs(vectorint nums, int startIndex) { for (int i 0; i path.size(); i) cout ; cout start startIndex path[; for (int v : path) cout v ,; cout ]\n; res.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]); dfs(nums, i 1); path.pop_back(); } }缩进随递归深度递增一眼就能看到整棵递归树的形状。如果发现同一个 path 重复出现在兄弟分支那大概率是去重条件不对如果发现递归永远在往深处走看看 startIndex 是不是忘了 1如果发现 path 里出现了从未选过的元素回头检查撤销操作是不是漏了 pop_back。这套方法对 93 题同样有效只是打印的东西改成字符串和 pointNum。调试字符串切割时我还会额外打印插入点之后 s 的当前完整串这样能很快发现 insert 之后 startIndex 偏移错误的问题。5.3 常见问题速查表我把这三道题刷下来遇到的典型问题总结成一个速查表。症状可能原因解法93 题结果少了几种合法切分循环里用了 continue 而非 break非法段后还在尝试更长的段改为 break93 题结果出现空最后一段终止条件里只判断了 pointNum 3没判断 startIndex 是否越界加上 startIndex s.size() 的判断93 题对“25525511135”程序崩溃stoi 转换超长数字导致异常手写 isValid 逐位累加78 题结果缺少空集和中间子集result.push_back 放在了终止条件里移到递归入口90 题结果出现重复子集没先排序或者去重条件写成 i 0先排序再改 i startIndex90 题结果丢失 [1,2,2]去重条件把树枝重复也跳过了确认 used 数组写法或 i startIndex90 题莫名其妙的跳过用了未排序的数组比较相邻元素排序放最前面这张表我建议直接存下来笔试的时候碰到类似回溯题先对照检查。6. 扩展子集问题不止回溯一种玩法6.1 位运算枚举全部子集回溯虽然是处理子集最通用的方法但不是唯一方法。如果数组长度 n 比较小一般不超过 20位运算枚举更简单直接。把每个元素看成二进制的一位1 表示选0 表示不选那么长度为 n 的数组的所有子集对应 0 到 (1n)-1 的所有整数。for (int mask 0; mask (1 n); mask) { vectorint subset; for (int i 0; i n; i) { if (mask (1 i)) subset.push_back(nums[i]); } res.push_back(subset); }这种写法没有递归没有去重问题代码非常短。但问题也明显n 一旦超过 202^n 这个规模就基本执行不动了而且它天然没有剪枝机制。回溯可以用约束条件提前砍掉大量分支位枚举则必须枚举完所有状态。6.2 回溯 vs 位运算怎么选我平时的选择标准是如果题目只让枚举所有子集且 n 很小位枚举更快如果题目带约束比如“元素和不超过 target”或者“必须包含某个元素”回溯剪枝优势就出来了。而且回溯能方便地处理去重位枚举处理去重要先排序再对相同元素做特殊处理麻烦得多。另外还有一类题用的是状压 DP 里的子集枚举比如给一个 mask枚举它的所有子集。经典写法是这个for (int sub mask; sub; sub (sub - 1) mask) { // 处理 sub }这个循环每次会把 sub 跳到下一个 mask 的子集时间复杂度是 O(2^k)k 是 mask 中 1 的个数。很多状压 DP 题用它做状态转移。如果搜索热词里出现“状压 dp 枚举子集”说的就是这件事它和回溯完全不是一个赛道但都属于“枚举子集”这个大的算法家族。6.3 提两个容易混淆的热词刷题圈最近流行“第 k 大子集和”它跟上面说的子集枚举有交集但考的是完全不同的技巧。核心办法通常是二分答案加计数或者折半枚举Meet in the Middlen 大一点还要配合优先队列。如果哪天你看到“第 k 大子集和”这个热词先去想二分答案能不能计数别上来就回溯硬枚举2^n 会直接超时。还有“NASA 公开的 N-CMAPSS 数据集子集DS02”这个跟算法题里的子集意思完全不一样。它说的是从完整数据集中抽出一部分样本做实验属于数据处理范畴跟回溯没有关系。搜索榜单里把这两个词放在一块纯粹是“子集”这个关键词撞车了。我个人实际刷完这三道题最大的体会是回溯题的代码框架真的不难难的是你愿不愿意画图。每次卡住把递归树画出来把每个节点的 path 写出来问题基本就能定位。一个很小但很实用的建议写之前先用纸笔把 78 题的递归树画出来标注哪些节点要收集哪些要跳过这一步比编译运行十次都管用。最后再分享一个我踩过的坑第一次提交 93 题的时候我用的是字符串插入法isValid 判断完直接 insert然后递归但忘在递归调用的时候传 i 2而是传了 i 1。结果就是每次插入点之后下一轮又会用到点后面的数字切出来的 IP 全是错的。所以如果你也用 insert 法记住这个 2 是关键或者干脆换成 vector 收集段的方式绕开这个坑。这三道题刷完之后建议你顺手把 17 电话号码的字母组合、131 分割回文串再过一遍。它们分别是“不同集合的排列”和“字符串切割”的变体跟这三道题合在一起回溯的基本盘就算彻底拿下了。 回溯算法三题精讲：子集、去重与IP切割
回溯算法大概是面试里最容易“一看就会一写就废”的题型。我刷到代码随想录 Day21 的时候三道题连排93 复原 IP 地址、78 子集、90 子集 II正好把回溯的三种经典场景全占了——字符串切割、全量枚举、重复元素去重。这篇文章不打算把模板背一遍就完事而是用三道题把“为什么这么写”彻底讲透看完你能直接照着重写一遍顺便把递归树打印的调试方法也学会。适合正在打基础刷题的人也适合准备面试想快速捡起回溯的朋友。好开始。1. 回溯问题的整体思路与三道题的定位1.1 回溯算法的核心思想与套路模板回溯说白了就是一棵隐式树的深度优先遍历。你在每个节点上做选择往深处走走不通就回头换一条路再走。这个“回头”的动作就是回溯。它解决的问题都有一个共同特征需要枚举所有满足条件的组合、子集或排列。代码随想录里给的模板特别精简我加了点自己的理解变成四个要素选择列表这一层 for 循环能选哪些元素。组合类问题通常用 startIndex 控制起点排列类问题用 used 数组控制是否用过。递归调用选了当前元素之后进入下一层参数跟着变。撤销操作从当前分支返回时把刚才加进 path 的元素弹出去恢复现场。终止条件什么时候把当前 path 存进结果。组合题是长度够了切割题是分割完成子集题比较特殊每个节点都要存。模板长这样void backtrack(参数) { if (终止条件) { 存放结果; return; } for (int i startIndex; i nums.size(); i) { path.push_back(nums[i]); // 处理节点 backtrack(新的参数); // 递归下一层 path.pop_back(); // 回溯撤销本层 } }这套模板的坑点不在模板本身而在三个问题上一是终止条件写在哪、怎么写二是结果收集放在递归入口还是终止条件里面三是循环里什么时候剪枝、什么时候去重。三道题正好各覆盖一个。1.2 三道题放在一起的递进逻辑为什么把这三道题放在同一天刷因为它们的递进关系非常明显。78 子集是基础让你理解“所有节点都是答案”这件事这跟组合问题“只收集叶子节点”是完全不同的思路。90 子集 II 是在 78 的基础上加了重复元素逼着你去处理去重。93 复原 IP 地址则是把回溯从“数组里选数字”上升到“字符串上做切割”处理的是索引和边界。我当时的感觉是78 全懂了90 就只是加了个排序和一行判断90 搞定后93 就是换了个收集结果的姿势但终止条件反而更绕。所以建议你也按这个顺序刷先 78 再 90 最后 93会有种一路打通的感觉。下面一道一道说。2. 93 复原 IP 地址字符串切割的边界与终止条件2.1 题意拆解与切割思路给一个只含数字的字符串要求往里面插三个点把它分成四段每段都是合法的 IP 地址段。合法条件是每段在 0 到 255 之间且不能有前导零——除了数字 0 本身是合法的一段像“01”这种就是非法。比如“25525511135”可以切成“255.255.11.135”和“255.255.111.35”。“0000”只能切成“0.0.0.0”因为“00”是非法前导零。“101023”能切成五种这里就不全列了后面调试部分会给完整输出。这种题天然适合回溯。你每次截取 1 到 3 位数字作为下一段截完用 isValid 检查一下合法就往字符串里插个点不合法就直接 break——为什么是 break 不是 continue因为 IP 段最多三位如果当前从 startIndex 截 i 位已经超了 255那再往长截只会更大后面的分支都不用看了。2.2 递归结构与终止条件怎么定很多人在终止条件这里犯迷糊。我用的是代码随想录的写法pointNum 表示已经插了几个点。终止条件不是判断 startIndex 到了字符串末尾而是判断 pointNum 3。因为插满 3 个点后还剩最后一段需要单独截取并校验校验通过才把整个串加入结果。这里有一个隐藏边界当 pointNum 3 时必须保证 startIndex s.size()也就是说最后一段不能是空串。否则像“255255”这种字符串切成“255.255.”最后一段空会被当成合法结果加进去这就是个明显的 bug。递归函数长这样参数s会被修改插入点的字符串、startIndex本轮切割起点、pointNum已插入的点数核心循环for (int i startIndex; i s.size(); i) { if (isValid(s, startIndex, i)) { s.insert(s.begin() i 1, .); // 在 i 后面插点 pointNum; backtrack(s, i 2, pointNum); // 点是间隔符所以下一轮起点 2 pointNum--; s.erase(s.begin() i 1); // 撤销插点 } else { break; } }注意 insert 之后原来下标 i 后面多了个点所以下一次递归的 startIndex 要传 i 2而不是 i 1。这个 2 是我第一次写的时候最容易漏的点漏了就死循环或者重复截取。2.3 IP 段合法性校验为什么不能直接用 stoiisValid 函数看起来很简单但我强烈建议别偷懒用 stoi原因后面说。先看手写版本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] 9 || s[i] 0) return false; // 非数字 num num * 10 (s[i] - 0); if (num 255) return false; // 超范围 } return true; }为什么不直接用 stoi两个原因。第一如果截出来的是“25525511135”这种超长字符串stoi 会直接抛出 out_of_range 异常程序崩溃你得先截短再转麻烦。第二stoi 没办法帮你判断前导零比如“01”转出来是 1看起来合法实际 IP 段不允许。手写循环的时候只要最高位是 0 且字符串长度大于 1就一定能拦住。2.4 复原 IP 地址最容易踩的三个坑第一个坑是 insert/erase 的索引偏移。插入点之后字符的位置整体右移撤销的 erase 操作要传同一个位置。我见过有人 insert 用了 i 1erase 却传 i结果字符串越删越乱。第二个坑是终止条件里没检查剩余字符。pointNum 3 时如果 startIndex 已经等于 s.size()说明最后一段是空的直接返回不进结果。第三个坑是循环里用了 continue 而不是 break。前面说了截取长度从 1 到 3 逐渐增加。当长度为 3 时 num 已经超过 255长度为 4 只会更大所以不需要继续试探break 能省掉所有无效分支。这个剪枝虽然不改变结果但能让递归树小不少。我也试过另一种写法不用字符串插入而是用 vectorstring ips 保存四段递归结束后再把四段拼成完整的 IP。这种实现避免 insert/erase 的索引问题思路更直观性能也更好。下面给个精简版class Solution { public: vectorstring restoreIpAddresses(string s) { if (s.size() 4 || s.size() 12) return {}; vectorstring res, seg; dfs(s, 0, res, seg); return res; } void dfs(string s, int start, vectorstring res, vectorstring seg) { if (seg.size() 4) { if (start s.size()) { res.push_back(seg[0] . seg[1] . seg[2] . seg[3]); } return; } for (int len 1; len 3 start len s.size(); len) { string part s.substr(start, len); if (!isValid(part)) continue; seg.push_back(part); dfs(s, start len, res, seg); seg.pop_back(); } } };这两种写法都行个人更推荐 vector 版逻辑清楚只是拼接的时候注意别多拼点。刷题阶段如果你能两个版本都写一遍对回溯的理解会更扎实。3. 78 子集在递归入口收集所有节点3.1 子集与组合、排列的本质区别先想一个问题组合题“组合总和 III”是在什么时候收集结果的是在 k 个元素都选完也就是叶子节点的地方。而子集题不一样[1][2][1,2] 这些中间状态通通都是答案。换句话说组合问题的答案是树的叶子子集问题的答案是整棵树的全部节点。这个区别直接决定了代码里 result.push_back(path) 放在哪里。如果你的代码是先判断终止条件再收集结果那最后收集的只有叶子空集和中间子集全丢了。排列问题的区别又不一样。排列不需要 startIndex因为每个位置都能重新选其他位置的元素所以要用 used 数组标记是否用过。子集和组合都用 startIndex 保证“后面的元素不回头选”这样才不会产生 [1,2] 和 [2,1] 这种重复。3.2 完整代码与收集时机分析78 子集的完整实现class Solution { public: vectorvectorint subsets(vectorint nums) { vectorvectorint res; vectorint path; dfs(nums, 0, res, path); return res; } void dfs(vectorint nums, int startIndex, vectorvectorint res, vectorint path) { res.push_back(path); // 每个节点都是子集先收集 if (startIndex nums.size()) return; // 没有可选元素就返回 for (int i startIndex; i nums.size(); i) { path.push_back(nums[i]); dfs(nums, i 1, res, path); path.pop_back(); } } };注意第一行就是 res.push_back(path)这一步已经在收集空集了。进入递归时 path 可能是空可能是 [1]可能是 [1,2]每个状态对应一个子集全部收进结果。然后才是判断 startIndex 是否越界。其实就算不写这个终止条件也能结束因为 for 循环在 i 到达 nums.size() 时自然结束但写上更清晰也符合回溯模板的习惯。3.3 复杂度与结果顺序时间复杂度是 O(n * 2^n)。为什么乘 n因为一共 2^n 个子集每个子集都需要拷贝一份 path 到 res 里拷贝一次最坏 O(n)。空间复杂度 O(n)递归深度最多 n 层path 存储 O(n)。还有个细节输出结果的顺序。以 [1,2,3] 为例我写的递归会得到 [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]这是按“前缀深度优先”的字典序不是从小到大的字典序。LeetCode 只要求包含所有子集不比较顺序所以没问题。但如果题目要求字典序输出你就需要收集完再排序或者调整递归顺序。4. 90 子集 II排序去重的两种写法4.1 重复元素为什么会生成重复子集90 题给的是 [1,2,2]数组中两个 2 是不同的元素但对结果来说它们是不可区分的。如果你用 78 的代码直接跑会得到 [[1,2(第一个2)], [1,2(第二个2)]] 这种视觉上重复的结果。重复的根源在于在同一层递归的 for 循环里如果前面已经选过一个 2后面又遇到一个相等的 2那么从第二个 2 出发的所有分支生成的子集跟前一个 2 的分支完全一样。解决原则就一句话先排序让相等的元素相邻然后在循环里跳过“同层已经处理过的重复元素”。4.2 树层去重 vs 树枝去重这是回溯去重里最经典的概念很多人在这里绕晕。我用树来拆解。树层指的是同一个父节点下面的多个分支也就是同一个 for 循环里的多次迭代。两个相同的元素如果出现在树层那么第二个分支是第一个分支的重复必须去掉。树枝指的是从根到某个叶子的单条路径也就是递归深入的过程。路径上允许出现重复元素比如 [1,2,2]这是合法子集因为两个 2 是数组里不同位置的两个值。很多初次接触的人会把这两者搞混写去重的时候连树枝的重复也一并砍掉结果 [1,2,2] 这个正确结果就没了。记住去重只去树层不去树枝。4.3 used 数组法与 startIndex 跳过法对比代码随想录里给了两种写法我都写出来对比一下。第一种used 数组法。需要额外维护一个 used 数组标记当前递归路径上哪些元素已经用过class Solution { public: vectorvectorint res; vectorint path; vectorvectorint subsetsWithDup(vectorint nums) { sort(nums.begin(), nums.end()); vectorbool used(nums.size(), false); dfs(nums, 0, used); return res; } void dfs(vectorint nums, int startIndex, vectorbool used) { res.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; dfs(nums, i 1, used); used[i] false; path.pop_back(); } } };这里的判断逻辑是当前元素和前一个元素相等且 used[i-1] 为 false说明前一个相同元素不在当前路径上它一定是本层 for 循环中已经处理完并回溯的元素所以当前元素属于树层重复跳过。如果 used[i-1] 为 true说明前一个 2 在路径上比如 [1,2,2] 这种情况这是树枝上的合法重复保留。第二种startIndex 跳过法。不需要 used 数组直接比较下标class Solution { public: vectorvectorint res; vectorint path; vectorvectorint subsetsWithDup(vectorint nums) { sort(nums.begin(), nums.end()); dfs(nums, 0); return res; } void dfs(vectorint nums, int startIndex) { res.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]); dfs(nums, i 1); path.pop_back(); } } };关键在 if (i startIndex)而不是 if (i 0)。因为每次递归都会重置起点为 startIndex如果写成 i 0会出现把合法的树枝重复也跳过的情况。只有 i startIndex 才能精确表达“本层 for 循环里已经处理过 nums[i-1]”。两种写法我实测下来startIndex 法代码更短used 数组法更通用——排列问题必须用 used 数组。建议都掌握至少要能讲清楚为什么一个用 used[i-1]false一个用 i startIndex。4.4 去重最容易犯的错第一个错是忘记排序。去重逻辑依赖相同元素相邻不排序的话 [1,2,1] 里两个 1 不相邻判断直接失效。所以先排序这是前提不是可选项。第二个错是在循环里直接写 if (nums[i] nums[i-1]) continue而没加 i startIndex 的判断。这样会把同一枝条内部的重复也拦掉[1,2,2] 的叶子子集直接被砍掉。第三个错是结果里出现重复元素也就是根本没去重。检查方法很简单跑一下 [1,2,2]输出应该是 [[], [1], [1,2], [1,2,2], [2], [2,2]]长度是 6。如果你输出里有两个 [2]那就是去重没生效。关于这一块后面《常见问题速查表》里我会把怎么检查列全。5. 实操过程、调试技巧与常见问题速查5.1 三道题的输出对照与自测用例写题不能只看逻辑要真的跑起来。我把三道题的关键自测用例和期望输出列成表方便你对照调试。题目输入期望输出93 复原 IP 地址25525511135[255.255.11.135, 255.255.111.35]93 复原 IP 地址0000[0.0.0.0]93 复原 IP 地址101023[1.0.10.23, 1.0.102.3, 10.1.0.23, 10.10.2.3, 101.0.2.3]78 子集[1,2,3][[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]90 子集 II[1,2,2][[], [1], [1,2], [1,2,2], [2], [2,2]]这些输出我都是实际跑过验证的。特别是 101023 这个用例覆盖了“0 单独成段”和“非 0 开头”的情况非常适合回归测试。你写完代码后先用这几个用例过一遍再随机生成几个字符串测试比如“123456789”这种没有合法切分的确保结果是空数组而不是死循环。5.2 状态打印法调试回溯回溯题最怕找不着 bug。我调试这类题的固定套路是在 dfs 入口打印当前层的信息包括递归深度、startIndex、当前 path、以及关键变量。以 90 题为例void dfs(vectorint nums, int startIndex) { for (int i 0; i path.size(); i) cout ; cout start startIndex path[; for (int v : path) cout v ,; cout ]\n; res.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]); dfs(nums, i 1); path.pop_back(); } }缩进随递归深度递增一眼就能看到整棵递归树的形状。如果发现同一个 path 重复出现在兄弟分支那大概率是去重条件不对如果发现递归永远在往深处走看看 startIndex 是不是忘了 1如果发现 path 里出现了从未选过的元素回头检查撤销操作是不是漏了 pop_back。这套方法对 93 题同样有效只是打印的东西改成字符串和 pointNum。调试字符串切割时我还会额外打印插入点之后 s 的当前完整串这样能很快发现 insert 之后 startIndex 偏移错误的问题。5.3 常见问题速查表我把这三道题刷下来遇到的典型问题总结成一个速查表。症状可能原因解法93 题结果少了几种合法切分循环里用了 continue 而非 break非法段后还在尝试更长的段改为 break93 题结果出现空最后一段终止条件里只判断了 pointNum 3没判断 startIndex 是否越界加上 startIndex s.size() 的判断93 题对“25525511135”程序崩溃stoi 转换超长数字导致异常手写 isValid 逐位累加78 题结果缺少空集和中间子集result.push_back 放在了终止条件里移到递归入口90 题结果出现重复子集没先排序或者去重条件写成 i 0先排序再改 i startIndex90 题结果丢失 [1,2,2]去重条件把树枝重复也跳过了确认 used 数组写法或 i startIndex90 题莫名其妙的跳过用了未排序的数组比较相邻元素排序放最前面这张表我建议直接存下来笔试的时候碰到类似回溯题先对照检查。6. 扩展子集问题不止回溯一种玩法6.1 位运算枚举全部子集回溯虽然是处理子集最通用的方法但不是唯一方法。如果数组长度 n 比较小一般不超过 20位运算枚举更简单直接。把每个元素看成二进制的一位1 表示选0 表示不选那么长度为 n 的数组的所有子集对应 0 到 (1n)-1 的所有整数。for (int mask 0; mask (1 n); mask) { vectorint subset; for (int i 0; i n; i) { if (mask (1 i)) subset.push_back(nums[i]); } res.push_back(subset); }这种写法没有递归没有去重问题代码非常短。但问题也明显n 一旦超过 202^n 这个规模就基本执行不动了而且它天然没有剪枝机制。回溯可以用约束条件提前砍掉大量分支位枚举则必须枚举完所有状态。6.2 回溯 vs 位运算怎么选我平时的选择标准是如果题目只让枚举所有子集且 n 很小位枚举更快如果题目带约束比如“元素和不超过 target”或者“必须包含某个元素”回溯剪枝优势就出来了。而且回溯能方便地处理去重位枚举处理去重要先排序再对相同元素做特殊处理麻烦得多。另外还有一类题用的是状压 DP 里的子集枚举比如给一个 mask枚举它的所有子集。经典写法是这个for (int sub mask; sub; sub (sub - 1) mask) { // 处理 sub }这个循环每次会把 sub 跳到下一个 mask 的子集时间复杂度是 O(2^k)k 是 mask 中 1 的个数。很多状压 DP 题用它做状态转移。如果搜索热词里出现“状压 dp 枚举子集”说的就是这件事它和回溯完全不是一个赛道但都属于“枚举子集”这个大的算法家族。6.3 提两个容易混淆的热词刷题圈最近流行“第 k 大子集和”它跟上面说的子集枚举有交集但考的是完全不同的技巧。核心办法通常是二分答案加计数或者折半枚举Meet in the Middlen 大一点还要配合优先队列。如果哪天你看到“第 k 大子集和”这个热词先去想二分答案能不能计数别上来就回溯硬枚举2^n 会直接超时。还有“NASA 公开的 N-CMAPSS 数据集子集DS02”这个跟算法题里的子集意思完全不一样。它说的是从完整数据集中抽出一部分样本做实验属于数据处理范畴跟回溯没有关系。搜索榜单里把这两个词放在一块纯粹是“子集”这个关键词撞车了。我个人实际刷完这三道题最大的体会是回溯题的代码框架真的不难难的是你愿不愿意画图。每次卡住把递归树画出来把每个节点的 path 写出来问题基本就能定位。一个很小但很实用的建议写之前先用纸笔把 78 题的递归树画出来标注哪些节点要收集哪些要跳过这一步比编译运行十次都管用。最后再分享一个我踩过的坑第一次提交 93 题的时候我用的是字符串插入法isValid 判断完直接 insert然后递归但忘在递归调用的时候传 i 2而是传了 i 1。结果就是每次插入点之后下一轮又会用到点后面的数字切出来的 IP 全是错的。所以如果你也用 insert 法记住这个 2 是关键或者干脆换成 vector 收集段的方式绕开这个坑。这三道题刷完之后建议你顺手把 17 电话号码的字母组合、131 分割回文串再过一遍。它们分别是“不同集合的排列”和“字符串切割”的变体跟这三道题合在一起回溯的基本盘就算彻底拿下了。