如果你正在刷回溯基本组合、子集之后大概率会撞上两道绕不开的题组合总和和复原IP地址。前者是“同一个元素能不能重复用”的去重问题后者是“字符串怎么切才合法”的分割问题。这两个问题表面上一类推数组、一类推字符串实际底层都是同一套回溯框架只是结束条件和去重逻辑换了换。这一篇就把这两类题放到一起拆开讲结合我自己刷题和给别人讲题时踩过的坑把细节抠明白。这篇内容适合谁看已经会写最基础的组合总和模板、但对去重和字符串分割还不熟的读者或者准备面试前想快速把回溯高频题过一遍的人。我会把模板、剪枝、去重为什么这么写、出错时怎么排查都按实操路子讲清楚。代码以 Java 为主思路本身换 Python、C 都一样用。1. 整体设计思路为什么两题放在一起学1.1 组合总和和复原IP地址的共同骨架回溯算法写的其实是“暴力枚举的优雅版本”。本质就是一件事在每一步尝试所有可能如果不符合预期就回退一步重新选。组合总和和复原IP地址放到一起学是因为它们的递归结构完全一致。组合总和的递归树是选择当前数字后下一层要么继续选同一个数字允许重复要么从下一个位置开始选不允许重复。复原IP地址的递归树是在当前字符串位置切一段下一层从切完的后面继续切。两者都是往递归函数里传一个 startIndex然后在这个 startIndex 开始的位置做选择选择完走下一层回来之后撤销选择。这两题的差别在于“怎么算一个合法选择”。组合总和里一个选择是否合法看数字和有没有超过 target复原IP地址里一段字符串是否合法看是不是在 0 到 255 之间、有没有前导零。理解了这一点你就知道为什么这两个题经常被放在同一个进阶章节里讲写代码的骨架一模一样难的是每道题各自不同的判断逻辑。1.2 学习顺序和思维拐点基础I通常覆盖的是“子集、组合、全排列、电话号码”这类入门题特征是递归参数好定义结果条件直接去重要求低。进入基础II之后思维拐点有两个。第一个拐点是从“选或不选”变成“选几个”。组合总和允许同一个数字无限次使用这意味着下一层递归不能总是 startIndex1而是要根据题意选择 startIndex 还是 startIndex 本身。这个点很多人第一次写都会懵容易把 i1 写进去后结果出现不了 [2,2,3] 这种合法组合或者在“当前数字能用多次”的情况下漏掉大量结果。第二个拐点是从“一维数组选择”变成“字符串切分”。数组选择问题是“选哪几个数字”字符串问题是“在哪里切几刀”。但一旦你意识到切片位置本身就是被枚举的索引两个问题就又重新统一了。IP地址固定四段这一条件恰好对应递归的固定深度这也是一个非常典型的回溯“终止条件”设计。2. 组合总和允许重复使用元素时的问题变体2.1 参数设计和递归含义先看最经典的一版。给定一个无重复元素的数组 candidates 和一个目标数 target找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取但解集不能包含重复的组合。这题的递归函数我会这样定义void backtrack(int[] candidates, int target, int startIndex, int sum)path当前已经选择的数字列表sum当前 path 里的数字和startIndex本层从 candidates 的哪个位置开始选startIndex 是核心。因为组合不强调顺序比如 [2, 3] 和 [3, 2] 算同一种组合所以每层只能从当前 startIndex 及之后的位置去选避免回头选之前的位置从而天然规避了“顺序不同的重复组合”。这也是为什么组合类问题用 startIndex、排列类问题用 used 数组的根本原因。允许重复使用元素体现在递归调用上就是backtrack(candidates, target, i, sum candidates[i])传的下一层起始索引是 i 而不是 i1。这样在同一层选完第 i 个数字后下一层依然能再选第 i 个实现了“同一个数字可重复使用”的效果。什么时候需要 i1组合总和II每个数字只能用一次的时候必须传 i1。这一个字符的差别就是两道题的本质分界。2.2 剪枝的先后顺序影响很大很多人写这题会发现不剪枝也能过但时间慢到离谱。剪枝最标准的做法是先把 candidates 排序然后在 for 循环开头判断if (sum candidates[i] target) break;这里能直接 break 而不是 continue是因为数组已经从小到大排序。如果当前这个数字加上去已经超过 target那后续更大的数字只会更超没有必要继续遍历。如果没排序就只能写 continue因为后面可能还有更小的数字能凑进去。排序这个操作看似多了一步实际上把整个搜索空间砍掉一大截。我试过不排序直接跑 LeetCode 39用例少的时候没感觉一到大数组合就开始超时边缘反复横跳。排序后基本都能稳定通过。这里还有一个容易被忽略的点sum 参数其实可以优化成 target 减去当前 path 的和。我习惯用 sum 累加也有很多人喜欢写 target 递减。两种写法本质一样但用递减写时结束条件变成if (target 0)剪枝条件变成if (target - candidates[i] 0) break逻辑也很顺。你在面试时用哪种都行关键是变量名要见名知意别写完自己再看都费劲。2.3 组合总和的完整实现最终我常用的版本如下class Solution { ListListInteger res new ArrayList(); ListInteger path new ArrayList(); public ListListInteger combinationSum(int[] candidates, int target) { Arrays.sort(candidates); backtrack(candidates, target, 0, 0); return res; } void backtrack(int[] candidates, int target, int startIndex, int sum) { if (sum target) { res.add(new ArrayList(path)); return; } for (int i startIndex; i candidates.length; i) { if (sum candidates[i] target) break; path.add(candidates[i]); backtrack(candidates, target, i, sum candidates[i]); path.remove(path.size() - 1); } } }一个小技巧是往 res 里添加结果时必须new ArrayList(path)直接res.add(path)会把引用存进去后面回溯修改 path 时已经存进 res 的内容也会跟着变输出结果会是一片空列表。这个问题在回溯新手代码里出现频率极高我排查过很多次基本都是这一行写错。组合总和的复杂度严格分析比较麻烦因为结果数量取决于具体数组和目标值。粗略可以认为搜索树是一棵每个节点分支数不超过 candidates.length 的树深度上限是 target 除以最小元素。空间复杂度主要看递归栈深度和 path 长度最坏到 O(target / min(candidates))。3. 组合总和II有重复元素时如何正确去重3.1 为什么会出现重复组合组合总和II是另一道经典题。给定数组 candidates 和一个目标数 target找出所有可以使数字和为 target 的组合。区别在于candidates 中的每个数字在每个组合里只能使用一次而且 candidates 里本身可能含有重复数字。这里最经典的例子是candidates [10, 1, 2, 7, 6, 1, 5], target 8。如果不做任何处理你会得到两组[1, 7]、两组[1, 2, 5]因为数组里有两个 1递归分别在两个 1 的位置展开了完全相同的结果。核心思路排序后在同一层遍历中如果当前数字和前一个数字相同说明前面那个数字作为本层起点的情况已经处理过了当前这个分支应该跳过。这一步在回溯里被称为“树层去重”。为什么要强调“树层”因为还有一个概念叫“树枝去重”两者是完全不同的情况。3.2 树层去重和树枝去重的区分“树层”指的是同一层递归里的多个并列分支。比如第一层分别选第一个 1、第二个 1这两个分支产生的结果会重复所以第二个 1 的分支要跳过。“树枝”指的是沿某一条递归路径往下走时的连续选择。比如选完第一个 1第二层又选了第二个 1形成组合[1, 1, 6]。这里的两个 1 在同一路径上属于正常情况不能跳过。代码上区分这两种情况最稳妥的是用一个 used 数组if (i 0 candidates[i] candidates[i - 1] !used[i - 1]) { continue; }这个条件怎么理解如果当前数字和前一个数字相同同时前一个数字没有被使用过说明前一个数字是在同一层被处理过然后回溯回来了。此时当前分支就是重复分支直接跳过。反过来如果前一个数字 used[i-1] 为 true说明它位于当前递归路径的上层也就是正在构造[1, 1, ...]这种合法路径此时不能跳过。3.3 更简洁的 startIndex 去重写法组合总和II还有一个更简练的写法不需要 used 数组直接在 for 循环开头写if (i startIndex candidates[i] candidates[i - 1]) { continue; }这行代码为什么也能去重因为 startIndex 是本层开始选择的索引。当 i startIndex 时说明当前遍历到的位置在本层已经是第二个及以后而前一个相同数字candidates[i-1]在本层已经被完整处理过递归回溯所以当前这个相同数字必然产生重复组合。相对比下used 数组写法适用范围更广尤其是在排列类问题里必须用它来保证每个元素只能用一次的同时正确处理同层去重。而 startIndex 写法代码更短但只适用于组合类问题。面试时最好两种都掌握提到组合总和II可以顺手解释两种写法的等价性会显得理解更深。完整实现class Solution { ListListInteger res new ArrayList(); ListInteger path new ArrayList(); public ListListInteger combinationSum2(int[] candidates, int target) { Arrays.sort(candidates); backtrack(candidates, target, 0, 0); return res; } void backtrack(int[] candidates, int target, int startIndex, int sum) { if (sum target) { res.add(new ArrayList(path)); return; } for (int i startIndex; i candidates.length; i) { if (sum candidates[i] target) break; if (i startIndex candidates[i] candidates[i - 1]) continue; path.add(candidates[i]); backtrack(candidates, target, i 1, sum candidates[i]); path.remove(path.size() - 1); } } }这里递归传的是 i1因为每个数字只能用一次。加上前面的排序和 break整体的剪枝比组合总和更狠基本每个节点都只遍历到能凑进 target 的位置。4. 复原IP地址回溯对象从数组变成字符串4.1 为什么字符串切分也能用回溯LeetCode 93题给定一个只包含数字的字符串 s返回所有可能的有效 IP 地址。典型输入25525511135输出[255.255.11.135, 255.255.111.35]。有效 IP 地址由四个整数组成每个整数位于 0 到 255 之间且不能含有前导零。比如01不合法但0本身合法。字符串分割问题和数组组合问题的对应关系是这样的把整个字符串看成数组每个可切割位置就是数组里的一次“选或不选”。但 IP 地址不是切到哪算哪而是必须恰好切成四段。这个“恰好四段”直接用递归深度控制就行。我用的递归函数void restoreIp(String s, int startIndex, int pointNum, String current)startIndex当前这一段的起始位置pointNum已经插入的点数量也就是已经确定了几段current当前已经拼接好的字符串递归终止条件不是 startIndex 到末尾而是 pointNum 3。这时只剩最后一段只要最后一段合法就能直接拼出答案。这里有个新手很容易犯的错pointNum 到 3 就直接 return没有判断剩余字符串是否合法导致结果少了一半甚至漏掉所有正确答案。4.2 合法段位的判断条件写恢复现场容易出错但比现场恢复更容易出错的是段位合法性判断。先定义一个工具方法private boolean isValid(String s, int start, int end) { if (start end) return false; if (s.charAt(start) 0 start ! end) return false; int num 0; for (int i start; i end; i) { num num * 10 (s.charAt(i) - 0); if (num 255) return false; } return true; }判断逻辑拆开看就三条段不能为空所以 start 必须小于等于 end如果段以 0 开头并且长度大于 1则非法例如01、023把段转成整数如果超过 255 则非法这个工具方法的时间复杂度是 O(段长度)而 IP 每段最多 3 位所以每次调用基本是常数时间不用过度优化。4.3 复原IP地址的实现与剪枝主逻辑里除了合法性判断还应该加上最少长度和最大长度的剪枝。IP 四段每段最短 1 位、最长 3 位。当前已经切了 pointNum 段剩余字符串长度必须在(4 - pointNum)到3 * (4 - pointNum)之间。用这个条件可以快速驳回很多不可能的分支。最终版本我倾向于不手动维护可变的 StringBuilder而是直接用 String 拼接传参。虽然字符串拼接在深递归时生成新对象但 IP 这个问题递归深度最多 4 层每层最多 3 个分支字符串拼接开销完全可接受代码可读性反而好很多class Solution { ListString res new ArrayList(); public ListString restoreIpAddresses(String s) { if (s.length() 4 || s.length() 12) return res; backtrack(s, 0, 0, ); return res; } void backtrack(String s, int startIndex, int pointNum, String current) { if (pointNum 3) { if (isValid(s, startIndex, s.length() - 1)) { res.add(current s.substring(startIndex)); } return; } for (int i startIndex; i s.length(); i) { if (i - startIndex 2) break; int remainLength s.length() - i - 1; int remainSegments 3 - pointNum; if (remainLength remainSegments || remainLength remainSegments * 3) continue; if (isValid(s, startIndex, i)) { backtrack(s, i 1, pointNum 1, current s.substring(startIndex, i 1) .); } else { break; } } } private boolean isValid(String s, int start, int end) { if (start end) return false; if (s.charAt(start) 0 start ! end) return false; int num 0; for (int i start; i end; i) { num num * 10 (s.charAt(i) - 0); if (num 255) return false; } return true; } }注意 for 循环里i - startIndex 2的 break。因为一段最多 3 位如果已经往后枚举了超过 3 个字符再长的段必然超过 255而且从 startIndex 开始的一段超过 3 位也不会合法所以直接 break。还要注意else break这个细节。为什么截取当前这段一旦不合法就 break 而不是继续因为字符串是从 startIndex 开始逐位增长的如果s.substring(startIndex, i1)已经是非法段位那么继续把 i 往后扩只会增加数字位数极大可能更不合法。比如从0开始01非法012也非法比如25合法到255合法到2551已经超过 255再往后25512也必然超过。所以这里直接 break 是安全的也带了很强的剪枝效果。这个题还有一个很容易踩的坑输入字符串长度。小于 4 位或大于 12 位都不可能有合法 IP直接返回空列表。别小看这个前置判断它能避免很多无效递归。我自己第一次做的时候忘了这个判断遇到超长输入直接开始跑结果肉眼可见地卡顿。5. 常见问题与排查技巧实录5.1 回溯高频错误速查表我把这几个问题放在一起做个速查表方便以后你写完代码跑不通时对照排查。现象可能原因排查方向组合总和结果缺失得不到用重复元素的组合递归传参写成了 i1确认允许重复使用元素的题下一层必须传 i组合总和II出现重复组合没排序或排序后没做树层去重数组先排序再加i startIndex判断组合总和II出现[1,1,6]被误杀去重条件写成了used[i-1]而不是!used[i-1]在纸上画递归树标清 used 的 true/false 状态复原IP地址结果为空pointNum3 时直接 return没校验最后一段把最后一段合法性判断放到终止条件里复原IP地址出现01.xxx这种结果isValid 里没排除前导零增加s.charAt(start) 0 start ! end判断最终结果全是空列表把 path 的引用直接 add 进了 res改成new ArrayList(path)递归跑不出结果或者死循环startIndex 或递归参数没有向终止方向推进检查每一层递归后 startIndex 是否变大或 pointNum 是否增加5.2 现场恢复没做好结果是“看起来对又不完全对”回溯里撤销选择就是“恢复现场”。组合总和里是path.remove(path.size() - 1)复原IP地址如果用 StringBuilder 就是 setLength 回退用 String 拼接则天然不需要手动恢复。很多初学者写递归时会在backtrack(...)之后忘记撤销导致下一分支选择时 path 里还残留上一分支的选择结果呈现“前缀重复”的诡异现象。我排查过最难受的一类问题是结果里混着半截错数据比如复原IP地址输出255.255.11.135和255.255.111.35都正常但偶尔冒出一个255.255.1111.35。这种基本就是 StringBuilder 在回溯时没有恢复到位应该回退的长度算错了。我的建议是能用不可变字符串拼接就用拼接能少维护状态就少维护。回溯已经够难了不要在状态管理上给自己加戏。5.3 画递归树的时间不要省组合总和和复原IP地址这两类题最值得投入时间的地方就是画递归树。不要只在脑子里想要真的在纸上画。以candidates[2,3,5], target8为例第一层从 2 开始下一层仍从 2 开始画三层就能看到[2,2,2,2]和[2,3,3]的分支差别。画到第四层时[2,2,2,2]已经达到 target 就往回走了而否则就会继续选。画树的过程中注意两点一是看每一层 for 循环的 i 从哪里开始二是看终止条件到达后是否有新的分支还可以再走。这两个位置掌握住回溯基本就不会跑偏。6. 关于这两个题我自己的实操总结组合总和和复原IP地址作为回溯基础II的典型代表最大的价值不是把两道题背下来而是把“组合类问题”和“字符串切分类问题”的解法和区分逻辑装进脑子里。我自己刷题时有一个习惯每次做完一道回溯题都去对比它和上一道题在三个位置上的差别。第一是递归函数的参数参数决定状态第二是 for 循环里的索引更新方式决定是取自身还是取下一个第三是剪枝条件决定这棵递归树能砍掉多少无效分支。对照完这三处基本上同一章节的题都能串起来。组合总和、组合总和II、复原IP地址、分割回文串、子集、全排列全都可以用这一套方法理解。甚至到后面的 N 皇后和数独也只是“如何判断一个选择是否合法”变得更复杂了递归框架仍然是那一套。有一点我踩过很多次坑特别想提醒你。如果你在面试或刷题时发现结果重复先别急着怀疑计算机先怀疑排序。组合总和II不去重十有八九不是代码跑错而是少了排序和树层去重。先排序再考虑去重逻辑问题基本迎刃而解。复原IP地址如果结果少了八成是终止条件没有把最后一段的合法性判断纳入进去而不是主逻辑有问题。这些坑都很小但每次都能消耗大量时间。把速查表留着下次写回溯卡住的时候拿出来对照一遍比重新翻题解快得多。