说实话看到这组题目标题的时候我第一反应是——这不就是一套完整递归搜索专题训练清单吗“子集异或和”“全排列II”“括号生成”“组合总和”“目标和”“字母大小写全排列”六个题串在一起覆盖了递归、搜索、回溯三大核心思想的绝大多数典型场景。你要是能把这一组题吃透笔试面试里碰到回溯类题目基本就稳了。很多初学者在刷这组题时容易陷入一个误区把每道题当成独立的题目去背代码、记模板结果过几天又忘了。实际上这几个题目背后只有一个东西——DFS搜索树 选择与撤销。你理解了这一层六个题就是一个题。这篇文章我会把这组题目串成一条线来拆先讲透回溯的通用框架再一个一个过核心题目重点讲每道题的“差异点在哪”“为什么这么写”最后汇总我刷这些题时踩过的坑和常用的排查思路。文章会给出核心代码片段但不会把每一行都贴出来毕竟代码自己能跑通才属于你自己。1. 回溯算法一套吃遍天下去的递归搜索框架1.1 为什么这几个题能归成一类先看题目清单里藏着的共性子集、组合、排列、括号、字母组合、表达式求值这些题看起来形态各异但本质上都在做同一件事——在多个决策步骤中每一步从若干可选方案里选一个穷举所有满足条件的完整路径。比如“找出所有子集”其实就是对每个元素做一次“选或不选”的决策全排列是每一层从剩余元素中选一个括号生成是每一步选左括号还是右括号。这些决策过程天然就是一棵多叉树而递归天然适合遍历树结构所以这类题的通用解法就是dfs递归遍历决策树。1.2 回溯的通用代码骨架我自己刷了几百道回溯题之后总结的模板基本固定成这个形状void backtrack(路径, 选择列表, 层数/索引等辅助参数) { if (满足结束条件) { 收集结果; return; } for (选择 : 当前层的选择列表) { 做选择; backtrack(更新后的路径, 更新后的选择列表, ...); 撤销选择; } }核心就三件事路径已经做出的选择、选择列表当前还可以做的选择、结束条件什么时候把路径记为答案。而“做选择”和“撤销选择”必须成对出现这是回溯区别于普通递归的关键——同一层递归结束后状态要恢复原样否则下一轮循环会拿到脏数据。这个模板看起来简单真正难的是怎么定义“选择列表”。有的题选择列表是固定的比如电话号码的字母映射有的题是动态的比如组合总和中的下一层起始索引有的题需要借助额外数组判断比如全排列II的重复元素剪枝。把这些搞明白模板就活了。1.3 “剪枝”之前先画递归树我一直强调一个习惯任何回溯题先画递归树再写代码。递归树画明白了代码就是照着树翻译一遍而已。举个例子“组合”问题从n个数中选k个的递归树长这样第一层选第一个数第二层只能从后面的数里选以此类推。画完之后你会发现每层递归的起始索引是上一层索引1这个规律直接决定了代码里startIndex参数怎么传。很多读者跳过画树直接写代码结果边界条件试半天不对。其实回溯题的大多数bug重复结果、漏结果、死循环都能通过画树定位——你只需要在纸上模拟一遍递归过程看看哪一步选择和树对不上。2. 题解拆解一子集异或和、组合、组合总和2.1 找出所有子集的异或总和再求和先学会“选或不选”这道题是LeetCode 1863题目要求枚举所有子集对每个子集求异或和再把所有子集的异或和加起来。为什么说这是回溯入门第一题因为它给的是最简单的“选择列表”——每个元素只有两种状态加入当前子集、不加入。对应到递归树上每个节点都分出两个分支整棵树是一棵二叉树深度就是数组长度。核心解法有两种写法我建议先掌握“选或不选”的递归写法class Solution { int sum 0; public int subsetXORSum(int[] nums) { dfs(nums, 0, 0); return sum; } void dfs(int[] nums, int index, int currentXor) { if (index nums.length) { sum currentXor; return; } // 不选当前元素 dfs(nums, index 1, currentXor); // 选当前元素异或值更新 dfs(nums, index 1, currentXor ^ nums[index]); } }注意这里有个细节currentXor作为参数传入时选与不选两个分支各自使用独立的异或值不需要显式“撤销”因为基本数据类型在递归调用时是值传递天然具备回溯效果。这一点和后面要讲的“路径用集合或列表时需手动撤销”不一样。另外说个优化思路这题其实存在数学解法——按位计算贡献。每个二进制位在子集中出现的次数决定了它对最终和的贡献。如果数组中某个元素在该位为1的元素个数为k那么该位为1的子集数量就是2^(n-1)只要至少选一个该位为1的元素最终该位的总贡献就是2^(n-1) * k * 该位的权值。这个做法的复杂度是 O(n log max(nums))但日常刷题用回溯就足够了。2.2 组合每层递归的控制条件组合LeetCode 77要求从[1, n]中选 k 个数输出所有组合。比如 n4, k2结果是[2,4], [3,4], [2,3], [1,2], [1,3], [1,4]。这题的关键是保证组合不重复且不遗漏。最常用的做法是引入startIndex每次递归从startIndex开始遍历选了当前数字i之后下一层从i1开始选。这样就天然避免了[1,2]和[2,1]这种重复组合。代码核心void backtrack(int n, int k, int startIndex, ListInteger path, ListListInteger res) { if (path.size() k) { res.add(new ArrayList(path)); return; } // 剪枝剩余可选数字不足时结束 for (int i startIndex; i n - (k - path.size()) 1; i) { path.add(i); backtrack(n, k, i 1, path, res); path.remove(path.size() - 1); } }这里有三个点需要特别说path.add(i)之后递归path.remove(path.size() - 1)就是撤销选择。因为path是同一个对象引用传递所有递归分支共享它所以必须手动撤销否则下一个分支会看到上一个分支留下的元素。收集结果时必须new ArrayList(path)直接把path加进去的话后续remove操作会把已经收集的结果也改掉。循环上限n - (k - path.size()) 1是剪枝优化意思是“当前位置至少要留出足够多的数填满剩余的坑”不写也能过但写了性能明显更好。2.3 组合总和去重逻辑与剪枝的精髓组合总和LeetCode 39和 组合总和IILeetCode 40是组合问题的升级版。第一件事要区分这两个题目组合总和candidates 中元素无重复每个元素可以无限次使用求所有和为 target 的组合。组合总和IIcandidates 中元素有重复每个元素只能使用一次求所有和为 target 的组合且结果不能重复。组合总和的递归写法只需要把上一题i1改成i代表下一层还可以继续选当前元素void backtrack(int[] candidates, int target, int startIndex, ListInteger path, int sum) { if (sum target) { res.add(new ArrayList(path)); return; } if (sum target) return; // 剪枝 for (int i startIndex; i candidates.length; i) { path.add(candidates[i]); backtrack(candidates, target, i, path, sum candidates[i]); path.remove(path.size() - 1); } }组合总和II的难点在去重。因为数组里有重复元素比如candidates [1, 1, 2]如果不去重第一层的两个1会分别生成[1,2]结果就重复了。标准解法是先将数组排序然后在同一层递归中跳过重复元素if (i startIndex candidates[i] candidates[i - 1]) continue;这个判断是“同一层去重”的经典写法。i startIndex保证的是当前循环不是本层的第一个元素且和前一个元素值相同。因为startIndex是当前层允许的最小索引i startIndex意味着当前不在本层第一个位置上此时如果值相同说明这个分支会生成和上一个分支相同的结果直接跳过。这个去重判断在“全排列II”中也会出现不过排列的去重写法略有不同后面我会专门对比。3. 题解拆解二全排列II、电话号码字母组合3.1 全排列II去重条件为什么是!used[i-1]全排列LeetCode 46和全排列IILeetCode 47的差异在是否存在重复元素。全排列的代码我觉得多数人都能背下来这里不重复。重点说全排列II的去重。题目输入[1, 1, 2]标准输出五种排列不能有重复。核心代码长这样void backtrack(int[] nums, boolean[] used, ListInteger path, ListListInteger res) { if (path.size() nums.length) { res.add(new ArrayList(path)); return; } for (int i 0; i nums.length; i) { if (used[i]) continue; // 同一层去重 if (i 0 nums[i] nums[i - 1] !used[i - 1]) continue; used[i] true; path.add(nums[i]); backtrack(nums, used, path, res); path.remove(path.size() - 1); used[i] false; } }去重判断是if (i 0 nums[i] nums[i - 1] !used[i - 1]) continue;很多人不理解为什么有!used[i-1]。这里我换一种方式解释假设数组是[1a, 1b, 2]其中两个 1 我们用a、b区分。全排列里同一数字出现在同一位置时1a在前和1b在前生成的序列是等价的。为了让结果去重我们需要约定重复元素之间保持原有顺序即1a永远排在1b之前。!used[i-1]的含义正是如果前一个相同元素1a还没被使用当前这个1b就不能使用因为那会打破顺序。而如果used[i-1]为 true说明1a已经在当前路径中那1b可以正常使用。对比一下组合总和II的去重组合题用的是if (i startIndex candidates[i] candidates[i-1]) continue;没有used数组是因为组合题通过startIndex天然限制了同一层遍历的起始位置只要在同一层循环中跳过重复值就够了。而排列题每层都从 0 开始遍历所有元素所以需要used数组来区分“哪些元素在当前路径中已使用”。这是两个题去重写法不同的根本原因。3.2 电话号码字母组合索引型回溯的典型电话号码字母组合LeetCode 17是另一个很经典的递归题目。数字 2-9 每个数字映射到一组字母输入一串数字输出所有可能的字母组合。这题可以看作选择列表固定的回溯第一层选择第一个数字对应的一个字母第二层选择第二个数字对应的一个字母依次类推。这里的“选择列表”不依赖之前的决策所以不需要额外的状态数组或者起始索引限制只需要一个index参数标记当前处理到第几个数字。String[] map {, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz}; void backtrack(String digits, int index, StringBuilder path, ListString res) { if (index digits.length()) { res.add(path.toString()); return; } String letters map[digits.charAt(index) - 0]; for (char c : letters.toCharArray()) { path.append(c); backtrack(digits, index 1, path, res); path.deleteCharAt(path.length() - 1); } }这题用StringBuilder做路径注意每次递归后要deleteCharAt撤销。也可以直接用String path做参数用字符串拼接path c这样不需要手动撤销——每个分支都创建了新的字符串对象。但刷题时推荐StringBuilder或ListCharacter因为字符串拼接会产生额外的内存分配性能差不少。这题其实也是后面很多字符串拼接类回溯题的基础模型一个索引从头走到尾每层从映射集合里选一个字符路径累积。3.3 括号生成合法性判断也是剪枝括号生成LeetCode 22要求生成 n 对括号的所有合法组合。很多人第一反应是先生成2n个位置的所有括号排列再去重、检查合法性。这样能过但性能很差。更好的思路是在生成过程中就保证合法性把“检查”变成“剪枝”。递归过程中维护两个计数left已放左括号数和right已放右括号数。每一步有两个选择——放左括号或放右括号但是只有当left n时才能放左括号只有当right left时才能放右括号右括号数量不能超过左括号数量否则当前前缀已经不是合法前缀了。void backtrack(int n, int left, int right, StringBuilder path, ListString res) { if (path.length() 2 * n) { res.add(path.toString()); return; } if (left n) { path.append((); backtrack(n, left 1, right, path, res); path.deleteCharAt(path.length() - 1); } if (right left) { path.append()); backtrack(n, left, right 1, path, res); path.deleteCharAt(path.length() - 1); } }注意这里每个节点最多只有两个分支和子集的“选/不选”模型相似但多了条件过滤。这个“每一步过滤非法选择”的思路非常通用后面“目标和”“字母大小写全排列”也用到了类似逻辑。4. 题解拆解三目标和、字母大小写全排列4.1 目标和从表达式求值到数组分堆目标和LeetCode 494题面给定非负整数数组nums和一个目标整数target在每个数前面添加或-求有多少种表达式结果等于 target。直观解法是回溯每个数有“加”和“减”两种选择深度为数组长度时间复杂度 O(2^n)。代码非常短int count 0; void backtrack(int[] nums, int index, int currentSum, int target) { if (index nums.length) { if (currentSum target) count; return; } backtrack(nums, index 1, currentSum nums[index], target); backtrack(nums, index 1, currentSum - nums[index], target); }这题和“子集异或总和”是同一种决策模型——每个元素两种状态只是子集题累积的是异或值这题累积的是加减和。但注意如果数组长度很大比如40纯回溯会超时。这时候可以把问题转换成背包问题设所有添加的数的和为P所有添加-的数的和为S那么P - S target又因为P S sum(nums)所以P (target sum(nums)) / 2。问题变成从数组中选若干个数使和为P的方案数——这就是 0/1 背包计数问题。这个转换是“目标和”这题的高级考点面试时如果能讲出来印象分会明显不同。4.2 字母大小写全排列字符串分支处理的技巧字母大小写全排列LeetCode 784要求给定一个字符串把其中的字母分别按大写、小写处理输出所有可能的排列。比如输入a1b2输出[a1b2,A1b2,a1B2,A1B2]等四种。这题的递归模型是从左到右遍历字符串遇到字母时分成两个分支转大写或转小写遇到数字时只有一个分支保持不变。路径可以用字符数组维护方便修改每个位置的字符。void backtrack(char[] arr, int index, ListString res) { if (index arr.length) { res.add(new String(arr)); return; } if (Character.isLetter(arr[index])) { arr[index] Character.toLowerCase(arr[index]); backtrack(arr, index 1, res); arr[index] Character.isUpperCase(arr[index]) ? Character.toLowerCase(arr[index]) : Character.toUpperCase(arr[index]); backtrack(arr, index 1, res); } else { backtrack(arr, index 1, res); } }这里有个小坑修改字符数组后从第一个分支回到第二个分支之前需要把字符恢复到原始状态或者利用大小写切换逻辑。上面代码用char判断并切换能省去额外保存的步骤但可读性稍差。更稳妥的方式是保留一个char original arr[index]两个分支分别设置original的大写和小写递归结束恢复original。回溯时“状态完全复原”原则在这个细节上体现得淋漓尽致。4.3 两个题的共通点分支条件决定结果正确性目标和与字母大小写全排列放在一起看能得出一个规律回溯框架相同关键在于每个节点的分支条件和状态更新方式。目标和是“加/减”两个分支更新的是当前累积和字母大小写全排列是“大写/小写”两个分支遇到数字则单分支更新的是当前索引位置的字符。两者都不需要预排序、不需要used数组因为问题本身没有“选择过的元素不能再用”的限制。这也再次说明做回溯题的核心是先搞清楚“每一步的状态是什么”“每一步有几种选择”“哪些选择合法”然后再去套模板。5. 通用排查技巧这组题最容易踩的坑5.1 结果重复结果重复最常见的原因是没有处理好“同一层去重”。组合总和II和全排列II尤其容易犯这个错误。排查方法在backtrack的开头加一行打印path内容 startIndex/used数组的状态跑一遍小规模用例观察是哪个分支生成了重复结果。我看到网上很多人的解法之所以去重失败是因为把去重条件写成了if (i 0 nums[i] nums[i-1])而忘了加!used[i-1]或者忘了i startIndex。记住去重的核心是“在同一层循环中相同的值只取第一个”。5.2 结果集被后续修改这个坑新手最容易踩res.add(path)而不是res.add(new ArrayList(path))。因为path是引用类型后续递归中的remove操作会直接修改已加入res的对象最终结果集里全是空列表或者最后一层状态。排查方法在收集结果的地方打印res的内容如果发现所有元素都一样那基本就是引用问题。这个错误我刷题早期至少犯过五次现在不管什么语言只要收集的是“可变对象”一律复制后加入结果集。5.3 死循环或栈溢出死循环大多源于递归参数没更新。比如组合总和中如果下一层还传startIndex而不是更新后的索引就会无限选择同一个元素。另外如果递归深度超过数组长度通常是结束条件写错比如应该index nums.length写成了index nums.length。遇到栈溢出不要慌先检查递归终止的 base case 是否能在有限步骤内到达。如果递归函数里有循环每次递归调用自己那就检查循环变量有没有在递归参数中体现。5.4 时间复杂度失控回溯的复杂度通常是 O(分支数^深度)指数级非常容易超时。遇到超时先画递归树数一下节点数然后确认是否能剪枝。常见的剪枝思路有排序后提前结束组合总和如果当前和已经超过 target直接return剩余元素数量不足时提前结束组合问题中n - (k - path.size()) 1剪枝使用used或visited数组避免无效分支把问题转换成背包、DP 等多项式算法如目标和。5.5 大小写切换的边界问题在做字母大小写全排列时很多人因为Character.toUpperCase和Character.toLowerCase混用导致分支重复或遗漏。我的习惯是在递归函数里先保存char temp arr[index]然后分支1设置为小写分支2设置为大写每个分支递归返回后统一执行arr[index] temp恢复现场。这样逻辑最清晰不会出bug。6. 把这些题串起来一套思路打天下6.1 六道题的差异对照表我用一张表把这六个题的差异点整理清楚刷题时对照着看效率很高。题目决策模型关键参数去重/剪枝要点时间复杂度子集异或和选/不选index基本类型参数无需手动撤销O(2^n)组合选一个后从后面继续startIndexstartIndex1 避免重复组合O(C(n,k))组合总和选一个后可重复选startIndex下一层仍传 i排序同层去重II指数级剪枝后可用全排列II从剩余元素中选used数组排序后!used[i-1]同层去重O(n!)电话号码字母组合从映射中选index无需去重天然互不相同O(4^n)括号生成两个条件分支left, rightleftn 与 rightleft 过滤非法O(Catalan(n))目标和加/减index前缀和剪枝可转背包O(2^n) / O(n*sum)字母大小写全排列大小写/单分支index恢复字符原状O(2^(字母数))看完这张表你会发现所有题都在index、startIndex、used、状态值这几种参数之间组合变化。index用于从头走到尾的线性扫描startIndex用于限制组合类问题不回头used用于排列类问题标记用过哪些元素状态值如 currentXor、sum、left/right则在递归过程中实时传递和更新。6.2 做题顺序建议如果你是新手我建议按这个顺序刷这组题子集异或总和——理解“选/不选”的最小模型组合——引入startIndex的概念组合总和II——在组合基础上去重全排列II——引入used数组去重对比组合去重差异电话号码字母组合——回归index模型练习映射括号生成——理解条件分支剪枝目标和——把前面的模型组合运用再学一下背包优化字母大小写全排列——练习字符串处理和状态恢复。这样安排的好处是每一步只引入一个新的概念不会一次性上来就让你面对一堆新名词。等你刷完这八道回溯的常规套路基本就刻在脑子里了。6.3 一个能提升刷题效率的习惯最后分享一个我自己的小习惯每道回溯题 AC 之后我都会做一次“三问复盘”——这道题的递归树长什么样如果去掉所有剪枝暴力枚举会生成多少结果剪枝条件做了什么数学上的推导这三个问题的答案如果都能说清楚说明这道题你是真懂了而不只是背下来了。特别是“目标和”那题如果没有想通P (targetsum)/2的推导过程下次换个数据范围你可能还是只能写暴搜。还有一个小技巧遇到不理解的递归过程拿一个很小的测试用例比如 n3手动在纸上跑一遍把每一层的path、startIndex、used都写出来。这个过程看起来很笨但真的比看十遍题解都管用。毕竟递归的调试本来就麻烦不如直接在脑内“人肉编译”。
说实话看到这组题目标题的时候我第一反应是——这不就是一套完整递归搜索专题训练清单吗“子集异或和”“全排列II”“括号生成”“组合总和”“目标和”“字母大小写全排列”六个题串在一起覆盖了递归、搜索、回溯三大核心思想的绝大多数典型场景。你要是能把这一组题吃透笔试面试里碰到回溯类题目基本就稳了。很多初学者在刷这组题时容易陷入一个误区把每道题当成独立的题目去背代码、记模板结果过几天又忘了。实际上这几个题目背后只有一个东西——DFS搜索树 选择与撤销。你理解了这一层六个题就是一个题。这篇文章我会把这组题目串成一条线来拆先讲透回溯的通用框架再一个一个过核心题目重点讲每道题的“差异点在哪”“为什么这么写”最后汇总我刷这些题时踩过的坑和常用的排查思路。文章会给出核心代码片段但不会把每一行都贴出来毕竟代码自己能跑通才属于你自己。1. 回溯算法一套吃遍天下去的递归搜索框架1.1 为什么这几个题能归成一类先看题目清单里藏着的共性子集、组合、排列、括号、字母组合、表达式求值这些题看起来形态各异但本质上都在做同一件事——在多个决策步骤中每一步从若干可选方案里选一个穷举所有满足条件的完整路径。比如“找出所有子集”其实就是对每个元素做一次“选或不选”的决策全排列是每一层从剩余元素中选一个括号生成是每一步选左括号还是右括号。这些决策过程天然就是一棵多叉树而递归天然适合遍历树结构所以这类题的通用解法就是dfs递归遍历决策树。1.2 回溯的通用代码骨架我自己刷了几百道回溯题之后总结的模板基本固定成这个形状void backtrack(路径, 选择列表, 层数/索引等辅助参数) { if (满足结束条件) { 收集结果; return; } for (选择 : 当前层的选择列表) { 做选择; backtrack(更新后的路径, 更新后的选择列表, ...); 撤销选择; } }核心就三件事路径已经做出的选择、选择列表当前还可以做的选择、结束条件什么时候把路径记为答案。而“做选择”和“撤销选择”必须成对出现这是回溯区别于普通递归的关键——同一层递归结束后状态要恢复原样否则下一轮循环会拿到脏数据。这个模板看起来简单真正难的是怎么定义“选择列表”。有的题选择列表是固定的比如电话号码的字母映射有的题是动态的比如组合总和中的下一层起始索引有的题需要借助额外数组判断比如全排列II的重复元素剪枝。把这些搞明白模板就活了。1.3 “剪枝”之前先画递归树我一直强调一个习惯任何回溯题先画递归树再写代码。递归树画明白了代码就是照着树翻译一遍而已。举个例子“组合”问题从n个数中选k个的递归树长这样第一层选第一个数第二层只能从后面的数里选以此类推。画完之后你会发现每层递归的起始索引是上一层索引1这个规律直接决定了代码里startIndex参数怎么传。很多读者跳过画树直接写代码结果边界条件试半天不对。其实回溯题的大多数bug重复结果、漏结果、死循环都能通过画树定位——你只需要在纸上模拟一遍递归过程看看哪一步选择和树对不上。2. 题解拆解一子集异或和、组合、组合总和2.1 找出所有子集的异或总和再求和先学会“选或不选”这道题是LeetCode 1863题目要求枚举所有子集对每个子集求异或和再把所有子集的异或和加起来。为什么说这是回溯入门第一题因为它给的是最简单的“选择列表”——每个元素只有两种状态加入当前子集、不加入。对应到递归树上每个节点都分出两个分支整棵树是一棵二叉树深度就是数组长度。核心解法有两种写法我建议先掌握“选或不选”的递归写法class Solution { int sum 0; public int subsetXORSum(int[] nums) { dfs(nums, 0, 0); return sum; } void dfs(int[] nums, int index, int currentXor) { if (index nums.length) { sum currentXor; return; } // 不选当前元素 dfs(nums, index 1, currentXor); // 选当前元素异或值更新 dfs(nums, index 1, currentXor ^ nums[index]); } }注意这里有个细节currentXor作为参数传入时选与不选两个分支各自使用独立的异或值不需要显式“撤销”因为基本数据类型在递归调用时是值传递天然具备回溯效果。这一点和后面要讲的“路径用集合或列表时需手动撤销”不一样。另外说个优化思路这题其实存在数学解法——按位计算贡献。每个二进制位在子集中出现的次数决定了它对最终和的贡献。如果数组中某个元素在该位为1的元素个数为k那么该位为1的子集数量就是2^(n-1)只要至少选一个该位为1的元素最终该位的总贡献就是2^(n-1) * k * 该位的权值。这个做法的复杂度是 O(n log max(nums))但日常刷题用回溯就足够了。2.2 组合每层递归的控制条件组合LeetCode 77要求从[1, n]中选 k 个数输出所有组合。比如 n4, k2结果是[2,4], [3,4], [2,3], [1,2], [1,3], [1,4]。这题的关键是保证组合不重复且不遗漏。最常用的做法是引入startIndex每次递归从startIndex开始遍历选了当前数字i之后下一层从i1开始选。这样就天然避免了[1,2]和[2,1]这种重复组合。代码核心void backtrack(int n, int k, int startIndex, ListInteger path, ListListInteger res) { if (path.size() k) { res.add(new ArrayList(path)); return; } // 剪枝剩余可选数字不足时结束 for (int i startIndex; i n - (k - path.size()) 1; i) { path.add(i); backtrack(n, k, i 1, path, res); path.remove(path.size() - 1); } }这里有三个点需要特别说path.add(i)之后递归path.remove(path.size() - 1)就是撤销选择。因为path是同一个对象引用传递所有递归分支共享它所以必须手动撤销否则下一个分支会看到上一个分支留下的元素。收集结果时必须new ArrayList(path)直接把path加进去的话后续remove操作会把已经收集的结果也改掉。循环上限n - (k - path.size()) 1是剪枝优化意思是“当前位置至少要留出足够多的数填满剩余的坑”不写也能过但写了性能明显更好。2.3 组合总和去重逻辑与剪枝的精髓组合总和LeetCode 39和 组合总和IILeetCode 40是组合问题的升级版。第一件事要区分这两个题目组合总和candidates 中元素无重复每个元素可以无限次使用求所有和为 target 的组合。组合总和IIcandidates 中元素有重复每个元素只能使用一次求所有和为 target 的组合且结果不能重复。组合总和的递归写法只需要把上一题i1改成i代表下一层还可以继续选当前元素void backtrack(int[] candidates, int target, int startIndex, ListInteger path, int sum) { if (sum target) { res.add(new ArrayList(path)); return; } if (sum target) return; // 剪枝 for (int i startIndex; i candidates.length; i) { path.add(candidates[i]); backtrack(candidates, target, i, path, sum candidates[i]); path.remove(path.size() - 1); } }组合总和II的难点在去重。因为数组里有重复元素比如candidates [1, 1, 2]如果不去重第一层的两个1会分别生成[1,2]结果就重复了。标准解法是先将数组排序然后在同一层递归中跳过重复元素if (i startIndex candidates[i] candidates[i - 1]) continue;这个判断是“同一层去重”的经典写法。i startIndex保证的是当前循环不是本层的第一个元素且和前一个元素值相同。因为startIndex是当前层允许的最小索引i startIndex意味着当前不在本层第一个位置上此时如果值相同说明这个分支会生成和上一个分支相同的结果直接跳过。这个去重判断在“全排列II”中也会出现不过排列的去重写法略有不同后面我会专门对比。3. 题解拆解二全排列II、电话号码字母组合3.1 全排列II去重条件为什么是!used[i-1]全排列LeetCode 46和全排列IILeetCode 47的差异在是否存在重复元素。全排列的代码我觉得多数人都能背下来这里不重复。重点说全排列II的去重。题目输入[1, 1, 2]标准输出五种排列不能有重复。核心代码长这样void backtrack(int[] nums, boolean[] used, ListInteger path, ListListInteger res) { if (path.size() nums.length) { res.add(new ArrayList(path)); return; } for (int i 0; i nums.length; i) { if (used[i]) continue; // 同一层去重 if (i 0 nums[i] nums[i - 1] !used[i - 1]) continue; used[i] true; path.add(nums[i]); backtrack(nums, used, path, res); path.remove(path.size() - 1); used[i] false; } }去重判断是if (i 0 nums[i] nums[i - 1] !used[i - 1]) continue;很多人不理解为什么有!used[i-1]。这里我换一种方式解释假设数组是[1a, 1b, 2]其中两个 1 我们用a、b区分。全排列里同一数字出现在同一位置时1a在前和1b在前生成的序列是等价的。为了让结果去重我们需要约定重复元素之间保持原有顺序即1a永远排在1b之前。!used[i-1]的含义正是如果前一个相同元素1a还没被使用当前这个1b就不能使用因为那会打破顺序。而如果used[i-1]为 true说明1a已经在当前路径中那1b可以正常使用。对比一下组合总和II的去重组合题用的是if (i startIndex candidates[i] candidates[i-1]) continue;没有used数组是因为组合题通过startIndex天然限制了同一层遍历的起始位置只要在同一层循环中跳过重复值就够了。而排列题每层都从 0 开始遍历所有元素所以需要used数组来区分“哪些元素在当前路径中已使用”。这是两个题去重写法不同的根本原因。3.2 电话号码字母组合索引型回溯的典型电话号码字母组合LeetCode 17是另一个很经典的递归题目。数字 2-9 每个数字映射到一组字母输入一串数字输出所有可能的字母组合。这题可以看作选择列表固定的回溯第一层选择第一个数字对应的一个字母第二层选择第二个数字对应的一个字母依次类推。这里的“选择列表”不依赖之前的决策所以不需要额外的状态数组或者起始索引限制只需要一个index参数标记当前处理到第几个数字。String[] map {, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz}; void backtrack(String digits, int index, StringBuilder path, ListString res) { if (index digits.length()) { res.add(path.toString()); return; } String letters map[digits.charAt(index) - 0]; for (char c : letters.toCharArray()) { path.append(c); backtrack(digits, index 1, path, res); path.deleteCharAt(path.length() - 1); } }这题用StringBuilder做路径注意每次递归后要deleteCharAt撤销。也可以直接用String path做参数用字符串拼接path c这样不需要手动撤销——每个分支都创建了新的字符串对象。但刷题时推荐StringBuilder或ListCharacter因为字符串拼接会产生额外的内存分配性能差不少。这题其实也是后面很多字符串拼接类回溯题的基础模型一个索引从头走到尾每层从映射集合里选一个字符路径累积。3.3 括号生成合法性判断也是剪枝括号生成LeetCode 22要求生成 n 对括号的所有合法组合。很多人第一反应是先生成2n个位置的所有括号排列再去重、检查合法性。这样能过但性能很差。更好的思路是在生成过程中就保证合法性把“检查”变成“剪枝”。递归过程中维护两个计数left已放左括号数和right已放右括号数。每一步有两个选择——放左括号或放右括号但是只有当left n时才能放左括号只有当right left时才能放右括号右括号数量不能超过左括号数量否则当前前缀已经不是合法前缀了。void backtrack(int n, int left, int right, StringBuilder path, ListString res) { if (path.length() 2 * n) { res.add(path.toString()); return; } if (left n) { path.append((); backtrack(n, left 1, right, path, res); path.deleteCharAt(path.length() - 1); } if (right left) { path.append()); backtrack(n, left, right 1, path, res); path.deleteCharAt(path.length() - 1); } }注意这里每个节点最多只有两个分支和子集的“选/不选”模型相似但多了条件过滤。这个“每一步过滤非法选择”的思路非常通用后面“目标和”“字母大小写全排列”也用到了类似逻辑。4. 题解拆解三目标和、字母大小写全排列4.1 目标和从表达式求值到数组分堆目标和LeetCode 494题面给定非负整数数组nums和一个目标整数target在每个数前面添加或-求有多少种表达式结果等于 target。直观解法是回溯每个数有“加”和“减”两种选择深度为数组长度时间复杂度 O(2^n)。代码非常短int count 0; void backtrack(int[] nums, int index, int currentSum, int target) { if (index nums.length) { if (currentSum target) count; return; } backtrack(nums, index 1, currentSum nums[index], target); backtrack(nums, index 1, currentSum - nums[index], target); }这题和“子集异或总和”是同一种决策模型——每个元素两种状态只是子集题累积的是异或值这题累积的是加减和。但注意如果数组长度很大比如40纯回溯会超时。这时候可以把问题转换成背包问题设所有添加的数的和为P所有添加-的数的和为S那么P - S target又因为P S sum(nums)所以P (target sum(nums)) / 2。问题变成从数组中选若干个数使和为P的方案数——这就是 0/1 背包计数问题。这个转换是“目标和”这题的高级考点面试时如果能讲出来印象分会明显不同。4.2 字母大小写全排列字符串分支处理的技巧字母大小写全排列LeetCode 784要求给定一个字符串把其中的字母分别按大写、小写处理输出所有可能的排列。比如输入a1b2输出[a1b2,A1b2,a1B2,A1B2]等四种。这题的递归模型是从左到右遍历字符串遇到字母时分成两个分支转大写或转小写遇到数字时只有一个分支保持不变。路径可以用字符数组维护方便修改每个位置的字符。void backtrack(char[] arr, int index, ListString res) { if (index arr.length) { res.add(new String(arr)); return; } if (Character.isLetter(arr[index])) { arr[index] Character.toLowerCase(arr[index]); backtrack(arr, index 1, res); arr[index] Character.isUpperCase(arr[index]) ? Character.toLowerCase(arr[index]) : Character.toUpperCase(arr[index]); backtrack(arr, index 1, res); } else { backtrack(arr, index 1, res); } }这里有个小坑修改字符数组后从第一个分支回到第二个分支之前需要把字符恢复到原始状态或者利用大小写切换逻辑。上面代码用char判断并切换能省去额外保存的步骤但可读性稍差。更稳妥的方式是保留一个char original arr[index]两个分支分别设置original的大写和小写递归结束恢复original。回溯时“状态完全复原”原则在这个细节上体现得淋漓尽致。4.3 两个题的共通点分支条件决定结果正确性目标和与字母大小写全排列放在一起看能得出一个规律回溯框架相同关键在于每个节点的分支条件和状态更新方式。目标和是“加/减”两个分支更新的是当前累积和字母大小写全排列是“大写/小写”两个分支遇到数字则单分支更新的是当前索引位置的字符。两者都不需要预排序、不需要used数组因为问题本身没有“选择过的元素不能再用”的限制。这也再次说明做回溯题的核心是先搞清楚“每一步的状态是什么”“每一步有几种选择”“哪些选择合法”然后再去套模板。5. 通用排查技巧这组题最容易踩的坑5.1 结果重复结果重复最常见的原因是没有处理好“同一层去重”。组合总和II和全排列II尤其容易犯这个错误。排查方法在backtrack的开头加一行打印path内容 startIndex/used数组的状态跑一遍小规模用例观察是哪个分支生成了重复结果。我看到网上很多人的解法之所以去重失败是因为把去重条件写成了if (i 0 nums[i] nums[i-1])而忘了加!used[i-1]或者忘了i startIndex。记住去重的核心是“在同一层循环中相同的值只取第一个”。5.2 结果集被后续修改这个坑新手最容易踩res.add(path)而不是res.add(new ArrayList(path))。因为path是引用类型后续递归中的remove操作会直接修改已加入res的对象最终结果集里全是空列表或者最后一层状态。排查方法在收集结果的地方打印res的内容如果发现所有元素都一样那基本就是引用问题。这个错误我刷题早期至少犯过五次现在不管什么语言只要收集的是“可变对象”一律复制后加入结果集。5.3 死循环或栈溢出死循环大多源于递归参数没更新。比如组合总和中如果下一层还传startIndex而不是更新后的索引就会无限选择同一个元素。另外如果递归深度超过数组长度通常是结束条件写错比如应该index nums.length写成了index nums.length。遇到栈溢出不要慌先检查递归终止的 base case 是否能在有限步骤内到达。如果递归函数里有循环每次递归调用自己那就检查循环变量有没有在递归参数中体现。5.4 时间复杂度失控回溯的复杂度通常是 O(分支数^深度)指数级非常容易超时。遇到超时先画递归树数一下节点数然后确认是否能剪枝。常见的剪枝思路有排序后提前结束组合总和如果当前和已经超过 target直接return剩余元素数量不足时提前结束组合问题中n - (k - path.size()) 1剪枝使用used或visited数组避免无效分支把问题转换成背包、DP 等多项式算法如目标和。5.5 大小写切换的边界问题在做字母大小写全排列时很多人因为Character.toUpperCase和Character.toLowerCase混用导致分支重复或遗漏。我的习惯是在递归函数里先保存char temp arr[index]然后分支1设置为小写分支2设置为大写每个分支递归返回后统一执行arr[index] temp恢复现场。这样逻辑最清晰不会出bug。6. 把这些题串起来一套思路打天下6.1 六道题的差异对照表我用一张表把这六个题的差异点整理清楚刷题时对照着看效率很高。题目决策模型关键参数去重/剪枝要点时间复杂度子集异或和选/不选index基本类型参数无需手动撤销O(2^n)组合选一个后从后面继续startIndexstartIndex1 避免重复组合O(C(n,k))组合总和选一个后可重复选startIndex下一层仍传 i排序同层去重II指数级剪枝后可用全排列II从剩余元素中选used数组排序后!used[i-1]同层去重O(n!)电话号码字母组合从映射中选index无需去重天然互不相同O(4^n)括号生成两个条件分支left, rightleftn 与 rightleft 过滤非法O(Catalan(n))目标和加/减index前缀和剪枝可转背包O(2^n) / O(n*sum)字母大小写全排列大小写/单分支index恢复字符原状O(2^(字母数))看完这张表你会发现所有题都在index、startIndex、used、状态值这几种参数之间组合变化。index用于从头走到尾的线性扫描startIndex用于限制组合类问题不回头used用于排列类问题标记用过哪些元素状态值如 currentXor、sum、left/right则在递归过程中实时传递和更新。6.2 做题顺序建议如果你是新手我建议按这个顺序刷这组题子集异或总和——理解“选/不选”的最小模型组合——引入startIndex的概念组合总和II——在组合基础上去重全排列II——引入used数组去重对比组合去重差异电话号码字母组合——回归index模型练习映射括号生成——理解条件分支剪枝目标和——把前面的模型组合运用再学一下背包优化字母大小写全排列——练习字符串处理和状态恢复。这样安排的好处是每一步只引入一个新的概念不会一次性上来就让你面对一堆新名词。等你刷完这八道回溯的常规套路基本就刻在脑子里了。6.3 一个能提升刷题效率的习惯最后分享一个我自己的小习惯每道回溯题 AC 之后我都会做一次“三问复盘”——这道题的递归树长什么样如果去掉所有剪枝暴力枚举会生成多少结果剪枝条件做了什么数学上的推导这三个问题的答案如果都能说清楚说明这道题你是真懂了而不只是背下来了。特别是“目标和”那题如果没有想通P (targetsum)/2的推导过程下次换个数据范围你可能还是只能写暴搜。还有一个小技巧遇到不理解的递归过程拿一个很小的测试用例比如 n3手动在纸上跑一遍把每一层的path、startIndex、used都写出来。这个过程看起来很笨但真的比看十遍题解都管用。毕竟递归的调试本来就麻烦不如直接在脑内“人肉编译”。
