回溯算法专题：从子集到全排列，一套框架拿下LeetCode搜索题

说实话，看到这组题目标题的时候，我第一反应是——这不就是一套完整递归搜索专题训练清单吗？“子集异或和”“全排列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 个数，输出所有组合。比如 n=4, k=2，结果是[2,4], [3,4], [2,3], [1,2], [1,3], [1,4]。

这题的关键是保证组合不重复且不遗漏。最常用的做法是引入startIndex，每次递归从startIndex开始遍历，选了当前数字i之后，下一层从i+1开始选。这样就天然避免了[1,2]和[2,1]这种重复组合。

代码核心：

void backtrack(int n, int k, int startIndex, List<Integer> path, List<List<Integer>> 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）和 组合总和II（LeetCode 40）是组合问题的升级版。

第一件事要区分这两个题目：

• 组合总和：candidates 中元素无重复，每个元素可以无限次使用，求所有和为 target 的组合。
• 组合总和II：candidates 中元素有重复，每个元素只能使用一次，求所有和为 target 的组合且结果不能重复。

组合总和的递归写法只需要把上一题i+1改成i，代表下一层还可以继续选当前元素：

void backtrack(int[] candidates, int target, int startIndex, List<Integer> 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）和全排列II（LeetCode 47）的差异在是否存在重复元素。

全排列的代码我觉得多数人都能背下来，这里不重复。重点说全排列II的去重。题目输入[1, 1, 2]，标准输出五种排列，不能有重复。核心代码长这样：

void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> 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, List<String> 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或List<Character>，因为字符串拼接会产生额外的内存分配，性能差不少。

这题其实也是后面很多字符串拼接类回溯题的基础模型：一个索引从头走到尾，每层从映射集合里选一个字符，路径累积。

3.3 括号生成：合法性判断也是剪枝

括号生成（LeetCode 22）要求生成 n 对括号的所有合法组合。

很多人第一反应是：先生成2n个位置的所有括号排列，再去重、检查合法性。这样能过，但性能很差。更好的思路是在生成过程中就保证合法性，把“检查”变成“剪枝”。

递归过程中维护两个计数：left（已放左括号数）和right（已放右括号数）。每一步有两个选择——放左括号或放右括号，但是：

• 只有当left < n时才能放左括号；
• 只有当right < left时才能放右括号（右括号数量不能超过左括号数量，否则当前前缀已经不是合法前缀了）。

void backtrack(int n, int left, int right, StringBuilder path, List<String> 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, List<String> 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、startIndex、used、状态值这几种参数之间组合变化。index用于从头走到尾的线性扫描，startIndex用于限制组合类问题不回头，used用于排列类问题标记用过哪些元素，状态值（如 currentXor、sum、left/right）则在递归过程中实时传递和更新。

6.2 做题顺序建议

如果你是新手，我建议按这个顺序刷这组题：

1. 子集异或总和——理解“选/不选”的最小模型；
2. 组合——引入startIndex的概念；
3. 组合总和II——在组合基础上去重；
4. 全排列II——引入used数组去重，对比组合去重差异；
5. 电话号码字母组合——回归index模型，练习映射；
6. 括号生成——理解条件分支剪枝；
7. 目标和——把前面的模型组合运用，再学一下背包优化；
8. 字母大小写全排列——练习字符串处理和状态恢复。

这样安排的好处是：每一步只引入一个新的概念，不会一次性上来就让你面对一堆新名词。等你刷完这八道，回溯的常规套路基本就刻在脑子里了。

6.3 一个能提升刷题效率的习惯

最后分享一个我自己的小习惯：每道回溯题 AC 之后，我都会做一次“三问复盘”——

• 这道题的递归树长什么样？
• 如果去掉所有剪枝，暴力枚举会生成多少结果？
• 剪枝条件做了什么数学上的推导？

这三个问题的答案如果都能说清楚，说明这道题你是真懂了，而不只是背下来了。特别是“目标和”那题，如果没有想通P = (target+sum)/2的推导过程，下次换个数据范围你可能还是只能写暴搜。

还有一个小技巧：遇到不理解的递归过程，拿一个很小的测试用例（比如 n=3）手动在纸上跑一遍，把每一层的path、startIndex、used都写出来。这个过程看起来很笨，但真的比看十遍题解都管用。毕竟递归的调试本来就麻烦，不如直接在脑内“人肉编译”。