刷力扣Hot100有一段时间了Java解法写了不少回溯这块是我反复觉得“看题解一秒懂、自己一写就废”的章节。尤其是全排列、子集、电话号码的字母组合、组合总和这四个题题面看起来八竿子打不着但递归树一画会发现它们共用同一套骨架递归函数里套一个 for 循环循环里做选择、进递归、撤销选择。难的不是模板而是模板上每个参数为什么这么设计——下一层从i还是i1开始、要不要used数组、要不要先排序、在哪个位置收集结果。这篇文章就把这四道力扣Hot100的题放在一起做一次系统复盘把每一处参数选择背后的理由、每一处剪枝的代价以及我实际写 Java 时踩过的坑都讲透。不管你是在面试前想集中刷一遍回溯还是刚开始刷题想找一个合适的入口这篇都适合拿来反复过两遍。1. 回溯算法的本质全排列是看透“状态树”最好的入口1.1 为什么先拿全排列开刀很多教程一开始就丢一个回溯模板出来问题是模板没被内化换一道题就不会套了。全排列是理解回溯最直观的入口因为它的状态树非常清晰以[1,2,3]为例第一层有三个选择选了 1 之后第二层只剩 2、3 两个选择第三层只剩最后一个数。整棵树从根到叶子一共有 3! 6 条路径每条路径就是一个排列。这个过程的本质是“每往下走一层就是决定当前位置放哪个数”。位置 0 放了 1后面就不能再放 1否则会出现重复元素。这就是used数组存在的意义——它不是去重而是记录“这条递归路径上哪些元素已经被占用了”。注意关键词是“这条路径”不是“全局”。所以在返回上一层之前必须把占用标记撤掉否则兄弟分支会看到被污染的状态。这里分享一个我自己的理解方式回溯就是带“后悔药”的深度优先搜索。普通的 DFS 走到叶子就结束回溯则要求你走完一条路之后退回到岔路口恢复现场再试另一条路。就像走迷宫你在走廊里留下的脚印只属于当前这条路试完死胡同就得擦掉脚印回到分岔点。1.2 全排列的Java实现与used数组的真相先给标准写法再拆每一步在干什么class Solution { public ListListInteger permute(int[] nums) { ListListInteger res new ArrayList(); ListInteger path new ArrayList(); boolean[] used new boolean[nums.length]; dfs(nums, path, used, res); return res; } private void dfs(int[] nums, ListInteger path, boolean[] used, ListListInteger res) { // 终止条件路径长度等于数组长度说明所有位置都填完了 if (path.size() nums.length) { res.add(new ArrayList(path)); return; } // 每一层都从 0 开始扫描所有元素 for (int i 0; i nums.length; i) { if (used[i]) { continue; } // 做选择 path.add(nums[i]); used[i] true; // 进递归 dfs(nums, path, used, res); // 撤销选择恢复现场 used[i] false; path.remove(path.size() - 1); } } }顺着代码走一条路径path先加nums[0]1标记used[0]进入下一层下一层从 0 扫描发现used[0]是 true 跳过于是加nums[1]2再下一层加nums[2]3。此时path.size()3保存[1,2,3]并返回。返回后撤销3的选择继续扫描发现没有别的候选了再返回上一层撤销2的选择此时下一轮i扫到nums[2]3于是走[1,3,2]这条分支。这里最容易犯的错误是忘记撤销used[i]。只撤销path不撤销used会导致某条分支走完之后兄弟分支里那些元素被永久“封印”结果少了一大堆组合。这在面试里属于比较低级的失误但压力状态下真有人会犯。复杂度也要能脱口而出一共有 n! 条路径每次到叶子深拷贝path需要 O(n)所以时间复杂度是 O(n! × n)。递归深度 npath和used各占 O(n) 空间不考虑结果集的话空间复杂度是 O(n)。面试官问复杂度时能答出这个通常印象分会加不少。2. 子集与全排列的“一字之差”把 used 换成 start2.1 子集的两种递归风格子集问题LeetCode 78的花样在于它的结果不只是叶子节点所有中间状态也都是合法子集。空集、单元素集、双元素集都要收进结果。第一次做的时候很容易在“什么时候收集结果”这里卡住。先看一种直觉写法叫“选或不选”private void dfs(int[] nums, int index, ListInteger path, ListListInteger res) { if (index nums.length) { res.add(new ArrayList(path)); return; } // 不选当前元素 dfs(nums, index 1, path, res); // 选当前元素 path.add(nums[index]); dfs(nums, index 1, path, res); path.remove(path.size() - 1); }这种写法把每个元素当成一个开关一路扫到底到叶子时才收集结果。逻辑非常干净也没有start、used这些概念。但它有一个问题不好扩展。一旦遇到组合总和这类“可以重复选”的题这个模型就僵住了。所以我在实际刷题里更推荐下面这种基于start的 for 循环写法class Solution { public ListListInteger subsets(int[] nums) { ListListInteger res new ArrayList(); ListInteger path new ArrayList(); dfs(nums, 0, path, res); return res; } private void dfs(int[] nums, int start, ListInteger path, ListListInteger res) { // 每一个节点的状态都是合法子集所以进入递归就先收集 res.add(new ArrayList(path)); for (int i start; i nums.length; i) { path.add(nums[i]); dfs(nums, i 1, path, res); path.remove(path.size() - 1); } } }关键点在于res.add放在递归函数的开头。这样进入dfs(nums, 0)时先收集空集然后 for 循环里收集单元素集递归进去再收集双元素集层层递进。这个设计非常巧妙也会在后面组合总和里继续用到。2.2 为什么全排列必须用 used子集必须用 start这是回溯里最核心的一个区分面试经常被追问。全排列是排列问题顺序敏感。[1,2,3]和[1,3,2]是两个不同的结果所以每个元素可以出现在任意位置每一层的选择范围都是“所有还没用过的元素”。为了知道哪些元素用过就必须引入used数组。子集是组合问题顺序不敏感。[1,2]和[2,1]在子集里是同一个东西。如果还用全排列那种“从 0 开始扫描”的做法就会出现大量重复。解决办法就是给选择加一个方向已经选了nums[2]后面只能从nums[3]开始继续选。这个“只能往后看”的约束就是start参数。打个生活化的比方全排列是给一群人排座位每个座位都可以坐任何没坐下的人所以你得记住谁已经坐下了子集是从班级里挑人去参加活动小组内部没有顺序你只需要从左到右扫一遍每个人决定“来不来”这样同一个小组不会被重复数两遍。本质上used管的是“同一个元素不能重复用”start管的是“不要生成顺序不同但内容相同的组合”。这两个东西别看长得不一样解决的问题完全不是一回事。2.3 进阶子集II的去重坑都在“i start”这一行Hot100 里的子集 II 加了重复元素限制比如[1,2,2]如果不处理会出现两个[2]、两个[1,2]。标准解法是先排序然后在 for 循环里加一行判断class Solution { public ListListInteger subsetsWithDup(int[] nums) { Arrays.sort(nums); ListListInteger res new ArrayList(); ListInteger path new ArrayList(); dfs(nums, 0, path, res); return res; } private void dfs(int[] nums, int start, ListInteger path, ListListInteger res) { res.add(new ArrayList(path)); for (int i start; i nums.length; i) { if (i start nums[i] nums[i - 1]) { continue; } path.add(nums[i]); dfs(nums, i 1, path, res); path.remove(path.size() - 1); } } }这里的判断条件是i start不是i 0。原因在于i start时当前元素是这一层第一个候选即使它和前一个数相等也代表一个全新的分支起点必须允许选择。只有当i start且当前数等于前一个数时说明在同一层重新选择了一个和之前候选一样的值这个分支和之前已经遍历过的分支完全重复才应该跳过。这行判断是整个回溯去重体系里最容易写错的地方。我见过不少人在子集 II 里写i 0结果连[2,2]这种合法子集都丢了。记结论时不要死记画出[1,2,2]的递归树自己走一遍i start时的逻辑比背一百遍都管用。3. 电话号码的字母组合把回溯从数组平移到了字符串3.1 映射表和递归参数怎么设计电话号码字母组合LeetCode 17和前面几题最大的不同是它没有数组只有一串数字而且每个数字对应多个字母。这题考查的是两个基本功一是映射表怎么建二是递归参数怎么定。映射表我建议直接用数组而不是MapInteger, String。原因很简单数字2到9正好是连续下标把digits的字符转成 int 就能直接查表省去 HashMap 的开销和类型转换class Solution { public ListString letterCombinations(String digits) { ListString res new ArrayList(); if (digits null || digits.length() 0) { return res; } String[] map {, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz}; dfs(digits, 0, new StringBuilder(), map, res); return res; } private void dfs(String digits, int index, StringBuilder path, String[] map, ListString res) { if (index digits.length()) { res.add(path.toString()); return; } String letters map[digits.charAt(index) - 0]; for (int i 0; i letters.length(); i) { path.append(letters.charAt(i)); dfs(digits, index 1, path, map, res); path.deleteCharAt(path.length() - 1); } } }digits.charAt(index) - 0是字符转数字的标准写法。有些新手会用Integer.valueOf(digits.substring(index, index 1))不是不行但没必要。char 做减法在 Java 里是非常自然的操作面试时写出来更干净。3.2 为什么这里不需要 used 数组这是这题最容易让人困惑的地方数字串里可能有重复数字比如22难道不需要记录哪个位置的数字用过吗答案是这里要管理的不是“元素是否可用”而是“当前处理到了第几位”。每个数字的位置是固定的递归参数index每次加 1天然保证每个 digit 都会被处理且只处理一次。这在本质上和全排列里的used是不同的模型全排列里元素可以放到任意位置所以位置和元素是解耦的电话号码里数字和位置是绑定的你不需要额外状态去防止重复。另一个需要注意的边界是digits为空。题目要求返回空列表而不是[]。很多初学者在这题上翻车就是因为没想明白“0 个数字组合出 0 个结果”和“1 个空结果”的区别。因为index digits.length()在最开始就不成立所以永远不会触发收集逻辑自然返回空列表。3.3 复杂度和一个常见追问digits里有些数字对应 3 个字母如 2、3、4、5、6、8有些对应 4 个字母7、9。假设输入里有 m 个三字母数字和 k 个四字母数字那么叶子节点一共有 3^m × 4^k 个。每个结果通过path.toString()构造需要 O(mk) 的时间所以总时间复杂度是 O((mk) × 3^m × 4^k)空间复杂度 O(mk) 的递归栈加结果集。面试里经常会有追问“如果 digits 特别长怎么办”这题的本质是要求穷举所有组合所以答案的数量本身就指数级你再怎么优化都逃不掉。能讨论的点在于可以改成流式生成或者用队列做 BFS不把所有结果同时存在内存里。但 LeetCode 场景下直接 DFS 收集就是最优解。顺便说一句用 StringBuilder 做路径容器比ListCharacter顺手得多特别是到叶子节点直接toString()就完事。但注意用完一定要deleteCharAt(path.length() - 1)这个撤销操作非常容易漏。4. 组合总和从 i1 改成 i一个字符解锁“无限重用”4.1 基本模板与“可以重复选”的代码差异组合总和LeetCode 39是回溯里最能体现“细节决定成败”的一道题。它允许无限制重复使用同一个候选数但要求结果去重。表面上看子集的代码稍加改动就能应付但关键就在一行下一层递归的起点是i而不是i 1。先看一个能过但不够优雅的版本class Solution { public ListListInteger combinationSum(int[] candidates, int target) { ListListInteger res new ArrayList(); dfs(candidates, target, 0, new ArrayList(), res); return res; } private void dfs(int[] candidates, int target, int start, ListInteger path, ListListInteger res) { if (target 0) { return; } if (target 0) { res.add(new ArrayList(path)); return; } for (int i start; i candidates.length; i) { path.add(candidates[i]); dfs(candidates, target - candidates[i], i, path, res); path.remove(path.size() - 1); } } }dfs第三个参数传的是i不是i 1。这意味着下一层仍然可以从当前下标开始选当前元素就能被重复使用。如果你改成i 1那每个元素最多用一次就变成组合总和 II 的规则了。一字符之差整道题的语义完全变化这就是回溯题最迷人的地方。这个版本把target 0当成终止条件写起来直观但代价是会产生很多无效递归。比如target已经很接近 0却还要先递归下去再判断负数白白浪费大量栈帧。更好的做法是把判断前置到循环里。4.2 剪枝排序之后continue 变 break剪枝的第一步是给candidates排序。排序本身 O(n log n) 的开销在回溯的指数复杂度面前可以忽略不计但收益非常大——一旦排好序candidates[i] target时后面的元素只会更大这时直接break跳出整个循环而不是用continue一个一个跳过class Solution { public ListListInteger combinationSum(int[] candidates, int target) { Arrays.sort(candidates); ListListInteger res new ArrayList(); dfs(candidates, target, 0, new ArrayList(), res); return res; } private void dfs(int[] candidates, int target, int start, ListInteger path, ListListInteger res) { if (target 0) { res.add(new ArrayList(path)); return; } for (int i start; i candidates.length; i) { if (candidates[i] target) { break; } path.add(candidates[i]); dfs(candidates, target - candidates[i], i, path, res); path.remove(path.size() - 1); } } }这个版本的代码量反而更少因为不需要target 0的判断了——循环里已经排除了所有会变成负数的情况。剪枝的思路不是“遇到不合法的就跳过”而是“在进入不合法区域之前就停下来”。用生活化的类比就是你在一排按价格排序的商品里挑预算内的东西看到第一个超预算的就可以直接走人不用把后面的全都翻一遍。4.3 组合总和II排序、i1、同层去重缺一个都不行组合总和 IILeetCode 40在 Hot100 里是同一系列区别是每个数字只能用一次。它把回溯三重考验集齐了排序去重、参数起点、同层剪枝。直接看代码class Solution { public ListListInteger combinationSum2(int[] candidates, int target) { Arrays.sort(candidates); ListListInteger res new ArrayList(); dfs(candidates, target, 0, new ArrayList(), res); return res; } private void dfs(int[] candidates, int target, int start, ListInteger path, ListListInteger res) { if (target 0) { res.add(new ArrayList(path)); return; } for (int i start; i candidates.length; i) { if (i start candidates[i] candidates[i - 1]) { continue; } if (candidates[i] target) { break; } path.add(candidates[i]); dfs(candidates, target - candidates[i], i 1, path, res); path.remove(path.size() - 1); } } }三个关键点必须同时出现缺一个答案就会错排序让重复元素相邻这是去重和break剪枝的前提。i 1每个元素只能用一次所以下一层从当前元素的下一个位置开始。i start candidates[i] candidates[i - 1]同层去重防止在同一个父节点下选择两个值相同的候选从而避免生成重复组合。为什么这个去重条件在子集 II 里见过在组合总和 II 里还能再用因为两个问题的本质完全一样在同一个 for 循环里如果当前候选和前一个候选数值相同说明你准备重复探索同一棵子树。排序之后这种重复都被压缩成相邻元素跳过即可。这里有一个很容易误解的点candidates[i] candidates[i - 1]只会跳过“同层重复”不会跳过“路径里不同层使用的相同值”。比如[1,1,2]中选[1,2]时第一个 1 和第二个 1 出现在不同层级这种是可以的因为它们在结果里代表不同的选择路径。这个边界建议自己手动推一遍candidates [1,1,2], target 3推完就再也不会搞混了。5. 四题同框一个模板、一张对照表、一堆 Java 细节5.1 回溯的万能模板四道题过完之后把它们的共性提炼出来就是下面这个模板void backtrack(参数列表, 路径状态, 结果集) { if (终止条件) { 结果集.add(路径状态的深拷贝); return; } for (候选 : 当前层的可选项) { if (剪枝条件) { continue; // 或者 break取决于是否已排序 } 路径状态.add(候选); backtrack(更新后的参数, 路径状态, 结果集); 路径状态.remove(路径状态.size() - 1); } }所有回溯题都逃不脱这个骨架。唯一的变量是终止条件怎么写、当前层的可选项是什么范围、剪枝条件是什么、路径状态用什么容器。把这几个变量想清楚代码自然就出来了。我在教学的时候经常告诉别人先别急着写把“递归树的每一层代表什么选择”想清楚。全排列每层选一个位置填哪个数子集每层决定是否加入当前元素电话号码每层选当前数字的一个字母组合总和每层选下一个候选数。层级清楚了参数设计就是顺水推舟的事。5.2 四道题的关键差异对照做题做多了脑子里要有这样一张表题目终止条件同层遍历起点允许重复选需要 used去重/剪枝关键全排列path.size() n每层从 0 开始否是无子集递归开头收集结果从 start 开始下一层 i1否否排序 i start 跳过电话号码字母组合index digits.length()当前数字对应字母串否否空串边界处理组合总和target 0从 start 开始下一层 i是否排序 break 剪枝组合总和 IItarget 0从 start 开始下一层 i1否否排序 同层去重这张表是我刷完几遍回溯题之后自己总结的比翻题解高效得多。你可以把表抄在笔记本上做题之前先对着表想一遍这道题属于哪一类、需要哪些参数、模板怎么变。复杂度也要记牢全排列 O(n! × n) 时间 O(n) 空间子集 O(2^n × n) 时间 O(n) 空间电话号码 O((mk) × 3^m × 4^k)组合总和最坏情况指数级别取决于 target 和候选数无法给出多项式上界。面试时能讲清这些已经超过大部分只背题解的候选人了。5.3 Java 细节踩坑清单代码正确性之外Java 实现里还藏着几个常见的坑每一个我都实际踩过结果集必须存深拷贝。res.add(path)是错的。path是递归过程里反复修改的同一个对象等你回溯回根节点时它已经变成空列表之前存进去的“结果”也会跟着变成空。正确写法永远是res.add(new ArrayList(path))。remove是按索引还是按对象。path.remove(path.size() - 1)明确按索引删除最后一个元素没问题。但如果你写path.remove(某个数字)Java 会把 int 当成索引而不是元素值。想按值删除得包一层Integer.valueOf而且如果有重复值它删的是第一个匹配不是最后一个——这就是定时炸弹。StringBuilder 的长度变化。递归之前append递归之后必须deleteCharAt(path.length() - 1)。漏掉它下一层分支会在错误的字符串基础上继续拼接。Deque和List的选择。全排列里有人爱用ArrayDeque做栈addLastremoveLast很顺手。但要注意Deque不接收 null而List无所谓。两种情况我都能接受关键是不要换来换去写顺手最重要。还有一个面试官爱追问的点“这个回溯为什么不需要标记已访问”答案取决于题目是“组合类”还是“排列类”。组合类问题靠start约束方向排列类问题靠used记录占用。把这条逻辑讲清楚比多刷十道题都有用。5.4 复盘心得与下篇预告我自己刷这几道题的体会是回溯题的瓶颈从来不是递归本身而是参数设计。很多人卡在“下一层该传什么出去”本质上是没想清楚“当前层的选择会如何影响后续选择”。used、start、index这三个参数分别对应三种不同的影响方式用完不能再用、只能往后选、必须处理下一个位置。把这三个参数和四种场景对应起来整类题型就通了。如果你现在也处于“题解看得懂、合上书写不出来”的状态我建议停下来找一道全排列把递归树亲手画一遍。画树的时间远比你想象中长但它能让你真正理解每个参数是在哪一层、为什么被那样设计。画完再上手写代码顺畅程度是完全不一样的。Hot100 里回溯还有不少进阶题比如分割回文串、N 皇后这类涉及“更复杂状态和更强约束”的题目等我把这部分沉淀完再出下篇继续拆。这四道题先吃透回溯的地基就算打牢了。