企业官网建设流程全解析

我最近集中刷完了一批回溯相关的 LeetCode 题目，从"找出所有子集的异或总和再求和"到"全排列 II"，再到"电话号码字母组合""括号生成""组合""目标和""组合总和""字母大小写全排列"，刷完之后最大的感受是：网上讲回溯的文章很多，但大多数把回溯讲得跟玄学一样——递归栈、状态恢复、剪枝条件、横向纵向去重，一套组合拳下来新手直接懵。

这个专题我可以负责任地说：回溯没有那么多花样，它本质上就是在一棵决策树上做深度优先遍历。你把树画出来，代码其实就是那三行模板的变体。所谓排列、组合、子集、字符串生成、括号匹配，全是在同一个模板上换"每层选什么"和"选了之后下一步从哪儿开始"而已。

这篇文章我会把这 8 道题的核心解法、代码模板、去重逻辑、剪枝时机全部串起来讲，重点解释"为什么这样写"，而不是只贴答案。尤其会讲清楚三个最容易被卡住的问题：startIndex到底怎么用、used数组去重的两种写法有什么区别、以及看上去和"排列组合"完全不沾边的题（比如括号生成、目标和）是怎么变成回溯题的。

如果你是正在准备算法面试，或者刚学到递归搜索这一章觉得似懂非懂，这篇文章应该能帮你把这几类题一次性理清楚。

1. 先把"回溯"这个东西看透：一棵决策树 + 三行模板

1.1 为什么所有回溯题都是同一棵树

回溯算法解决的核心问题是：在多个选择面前，穷举所有可能路径。

我说的"穷举"不是暴力 for 循环那种穷举，而是一种带状态的分步穷举。想象你在一个岔路口，面前有三条路，你选了第一条走进去，发现前面又是岔路口，又得选一条，就这样一层层走下去，直到走不动为止。走到头之后，你退回到上一个岔路口，换另一条路继续走。

这个"走进去再退出来"的过程，就是回溯（backtracking）。递归天然支持这种"进入下一层再返回上一层"的行为，所以回溯总是和递归一起出现。

你把这 8 道题全部套进这个模型里看一下：

• 子集异或总和：每个元素选 or 不选，二叉决策树。
• 全排列 II：每层从剩余元素中选择一个排到当前位置，多叉决策树。
• 电话号码字母组合：第一个数字对应的字母中选一个，第二个数字对应的字母中选一个，每层选择集合不同，多叉树。
• 括号生成：每层选择放左括号还是右括号，二叉决策树。
• 组合：从 n 个数中选 k 个数，每层决定当前位置放哪个数，多叉树。
• 目标和：每个数前面放正号还是负号，二叉决策树。
• 组合总和：每个位置从候选数中选一个，允许重复选，多叉树。
• 字母大小写全排列：每个字母选择大写还是小写，二叉决策树。

所以你看，题目千变万化，底层都是同一棵树。你只要学会把问题抽象成"树的每一层代表一个决策节点，每个分支代表一种选择"，代码就是顺水推舟的事。

1.2 那个让你背下来的三行模板到底在干嘛

回溯代码流传最广的模板大概是这样的：

def backtrack(路径, 选择列表): if 满足结束条件: 结果.append(路径) return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择

很多人背下来了但不知道为什么。我拆给你看：

• backtrack(路径, 选择列表)：走到当前节点时，已经做出的选择记录在"路径"里，接下来还能做什么选择记录在"选择列表"里。这个函数的功能是：在当前状态下，尝试所有可能的选择，并继续往下走。
• if 满足结束条件：走到树的叶子节点或者满足题目要求的目标状态时，把当前路径保存下来，不再往下走。
• for 选择 in 选择列表：当前层所有可选的分支，一个分支一个分支地尝试。
• 做选择：把当前选择追加到路径里，同时更新选择列表。
• backtrack：带着新状态进入下一层。
• 撤销选择：回到当前层时，把刚才的选择从路径里删掉，恢复现场，准备尝试下一个分支。

这里最关键的一步是撤销选择。因为选择列表和路径在很多实现里是共用的可变对象（比如同一个列表），你不撤销上次的选择，下一个分支就会带着脏数据往下走。这就是老手常说的"恢复现场"。

提示：如果你不想手动撤销，可以每次递归时传一个新构造的列表，比如path + [num]，但这会产生大量临时对象，数据量大的时候内存和耗时都会明显上升。刷题阶段无所谓，但理解"撤销"才能写出高效写法。

1.3 path、used、startIndex 三个变量的真实含义

这三个变量是回溯题的"灵魂三件套"，很多题就是围绕它们做文章：

• path：当前路径，即已经做出的选择序列。比如全排列中已经排好的前几个位置。
• used：记录某个元素是否已经被使用。只有排列类问题需要它，因为排列看顺序，第 i 层和第 j 层可能用到同一个元素，但一个元素不能同时出现在两个位置。
• startIndex：记录下一层从哪个位置开始枚举。组合和子集类问题需要它，因为组合不关心顺序，[1,2]和[2,1]是同一个组合，通过强制"下一层只能从当前元素之后开始选"来避免重复组合。

很多人的困惑在于：什么时候用used，什么时候用startIndex？一句话总结：

• 每个元素可以被不同位置的递归层重复考虑，但同一时刻只能用一次（排列、元素不能重复使用的子集/组合）→ 用used或startIndex。
• 每个元素在不同层可以被重复选择同一个（组合总和）→ 用startIndex，但进入下一层时不+1。
• 每个元素只有两种选择状态（选/不选、大写/小写、左括号/右括号）→ 不需要这两个变量，直接带状态往下递归即可。

后面我会结合具体题一个个过。

2. 组合与子集：startIndex 是这一类题的命门

2.1 子集问题：每次递归都记录

先看最简单的一组：子集类型。标题里的"找出所有子集的异或总和再求和"（LeetCode 1863）看起来很长，拆开就是两件事：先找出所有子集，再把每个子集的异或总和加起来。

如果只是枚举所有子集，代码可以写成这样：

def subset_xor_sum(nums): n = len(nums) res = [] path = [] def dfs(idx): res.append(path[:]) # 每个节点状态都是一个子集 for i in range(idx, n): path.append(nums[i]) dfs(i + 1) path.pop() dfs(0) return res

注意我写的是res.append(path[:])，这里如果写成res.append(path)，最后结果会全是空列表。原因就是 path 在递归过程中被反复修改，你 append 的是引用，后面path.pop()会把已经存进去的内容也改掉。这个坑我刷题早期踩过 N 次，现在已经是肌肉记忆了：凡是把可变对象存入结果集合，必须拷贝一份。

回到 LeetCode 1863，如果你先枚举子集再逐个算异或和，也能 AC，因为n最多 12，复杂度 2^12=4096，怎么算都很快。但我更建议你顺手做一个小优化：在递归过程中直接维护当前子集的异或值，每层把当前异或值累加到答案里，省掉最后再遍历一遍子集的开销。

def subset_xor_sum(nums): n = len(nums) total = 0 def dfs(idx, cur_xor): nonlocal total total += cur_xor for i in range(idx, n): dfs(i + 1, cur_xor ^ nums[i]) dfs(0, 0) return total

这个写法里，每个节点进入时cur_xor代表当前路径的异或值，进入第一层时cur_xor=0对应空子集，恰好空子集的异或和是 0，不影响结果。这个题有个更数学的做法是按位拆贡献，但面试时用回溯已经足够，还会显得你思路自然。

2.2 组合：卡住长度再收

LeetCode 77 组合，从1~n中选k个数。和子集的唯一区别是：子集在每个节点都把 path 记录下来；组合只在path 长度等于 k的时候记录。

def combine(n, k): res = [] def dfs(start, path): if len(path) == k: res.append(path[:]) return for i in range(start, n + 1): path.append(i) dfs(i + 1, path) path.pop() dfs(1, []) return res

这里start的作用是强制让数字按升序出现，于是[1,2]会出现，而[2,1]永远不会出现，天然去重。

这个题有个经典剪枝：如果当前 path 的长度加上剩余可选数字个数都不足 k，就没必要继续递归了。用公式表示就是：

if len(path) + (n - i + 1) < k: break

放在 for 循环里可以省掉大量无效递归。对 n=20、k=15 这种数据能明显感受到差异，面试时主动提出来是加分项。

2.3 组合总和：允许重复选时，下一层从哪开始？

LeetCode 39 组合总和，候选数组无重复，但每个数字可以被无限次选择。这题的代码只改一行：进入下一层递归时，从i开始而不是i+1。

def combination_sum(candidates, target): res = [] path = [] def dfs(start, remain): if remain == 0: res.append(path[:]) return if remain < 0: return for i in range(start, len(candidates)): path.append(candidates[i]) dfs(i, remain - candidates[i]) # 注意是 i，不是 i+1 path.pop() dfs(0, target) return res

为什么从i开始就能允许重复？因为当前选了candidates[i]之后，下一层还能继续选它，这就是"无限使用"的含义。而通过start=i又保证了不会走回头路去选下标更小的元素，避免了组合的重复。

这里可以加一个剪枝：先把 candidates 排序，如果candidates[i] > remain，那么后面的元素全部大于 remain，直接 break。因为候选数组里都是正数，当前都放不进去了，更大的更放不进去。这个剪枝在 target 很大、candidates 很长时效果非常明显。

2.4 去重的本质：同一层不放相同元素

组合总和有个进阶版 LeetCode 40，候选数组里含重复数字，每个数字只能用一次。这种题必须先排序，然后在 for 循环里加一行判断：

if i > start and candidates[i] == candidates[i - 1]: continue

这一行的含义是：在同一层递归中，如果当前元素和前一个元素相等，跳过。因为相同值的两个元素在同一层会产生完全相同的分支，保留一个就够了。

很多人的困惑是：排序之后相邻重复元素被跳过，会不会漏掉[1,1,2]这种需要两个不同位置的 1 同时出现的组合？不会。因为跳过的是"同一层"的重复，[1,1,2]里的两个 1 是分别在两层选中的，不是同一层选了两次。仔细体会这句话："同一层"三个字是去重的核心边界。

3. 排列问题：全排列 II 为什么必须用 used 数组

3.1 排列和组合在代码上到底差在哪

组合用startIndex避免回头，排列则不同——排列里每个元素都可能出现在任意位置。比如[1,2,3]的全排列，第一个位置选了 2，第二个位置还能选 1 或 3，所以不能用startIndex限制"从哪开始"，而必须用一个used数组标记哪些元素已经用过。

LeetCode 46 全排列的基础代码：

def permute(nums): res = [] used = [False] * len(nums) def dfs(path): if len(path) == len(nums): res.append(path[:]) return for i in range(len(nums)): if used[i]: continue used[i] = True path.append(nums[i]) dfs(path) path.pop() used[i] = False dfs([]) return res

注意这里和组合类问题最大的代码差异：循环每次都从 0 开始遍历，但通过used数组过滤掉已经用过的元素。排列类型没有startIndex，这是判断这类题型最明显的标志。

3.2 used[i-1] 的两种判法有什么区别

LeetCode 47 全排列 II，在 46 的基础上允许输入包含重复数字。如果直接用 46 的代码，会产生重复排列。去重手段和组合去重一样：先排序 + 在同一层跳过重复元素，但具体写法有两种。

第一种写法：

if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]: continue

第二种写法：

if i > 0 and nums[i] == nums[i - 1] and used[i - 1]: continue

两种写法都能去重，但语义不同，很多人在这里翻车。我建议你记住第一种，也就是not used[i - 1]。它的含义是：当前元素和前一个元素相同，且前一个元素在刚刚的递归回溯中已经被撤销了，说明当前是在同一层枚举重复值，跳过。这个判断保留的是"最左边那个相同的元素"产生的分支，其余重复元素在同一层直接剪掉。

第二种写法used[i-1] == True表示保留的是"最右边那个相同元素"的分支，需要前一个元素处于使用中才允许继续。它也能去重，但配合后续代码时，如果其他剪枝条件写得不小心，容易产生逻辑混乱。所以统一用not used[i-1]这种写法最稳。

def permute_unique(nums): nums.sort() res = [] used = [False] * len(nums) def dfs(path): if len(path) == len(nums): res.append(path[:]) return for i in range(len(nums)): if used[i]: continue if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]: continue used[i] = True path.append(nums[i]) dfs(path) path.pop() used[i] = False dfs([]) return res

3.3 全排列 II 去重容易翻车的一个细节

去重判断里必须是nums[i] == nums[i-1]，这个没问题，但你必须保证数组是排序过的。如果你在原数组无序的情况下加同样的判断，去重会失效，还会误杀一些本应存在的排列。

另一个容易翻车的地方是：if used[i]: continue必须放在去重判断之前。因为如果当前元素已经被使用，无论它是不是重复元素，都得跳过，这是第一道闸门。顺序反了虽然有时候结果也对，但逻辑上是错的，一旦数据集复杂，bug 会非常难查。

4. 字符串生成与形态转化：把"选择"换个说法

4.1 电话号码字母组合：每层可选项由当前数字决定

LeetCode 17，输入一个数字字符串如 "23"，2 对应 "abc"，3 对应 "def"，返回所有可能的字母组合。

这题的抽象方式和前面的数字组合完全一样，区别只是每一层的候选集合不一样：第 0 层的候选集由 digits[0] 决定，第 1 层由 digits[1] 决定。所以代码里需要一个 index 记录当前处理到第几个数字，for 循环遍历的是这个数字对应的字母。

def letter_combinations(digits): if not digits: return [] mapping = { '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz' } res = [] def dfs(idx, path): if idx == len(digits): res.append(''.join(path)) return for ch in mapping[digits[idx]]: path.append(ch) dfs(idx + 1, path) path.pop() dfs(0, []) return res

这段代码里没有used也没有startIndex，因为每个字母只对应一种选择路径，不需要互相之间避免冲突。这题的意义在于让你认识到：回溯模板里的"选择列表"不一定是全局固定的，它可以由当前递归层级动态计算。这是从"数组组合"跨越到"字符串/其他复杂状态"的桥梁。

4.2 括号生成：用剩余数量控制合法性

LeetCode 22，生成 n 对括号的所有合法组合，比如 n=3 时包括((()))、(()())等 5 个。

这题如果先穷举所有括号序列再判断合法性，2^(2n) 个可能性，n=10 就已经接近 100 万了，性能不够优雅。更聪明的做法是：在生成过程中就保证序列始终合法。

合法括号序列有两个硬性条件：

1. 左括号数量不超过 n。
2. 在任何一个前缀里，右括号数量不超过左括号数量。

把这两个条件转化成回溯的剪枝条件就是：

def generate_parenthesis(n): res = [] def dfs(left, right, path): if len(path) == 2 * n: res.append(''.join(path)) return if left < n: path.append('(') dfs(left + 1, right, path) path.pop() if right < left: path.append(')') dfs(left, right + 1, path) path.pop() dfs(0, 0, []) return res

注意if right < left这个条件，它保证任何时刻右括号数量不会超过左括号，于是生成的每个前缀都是合法的。你不需要在最后检查括号匹配，因为剪枝条件已经把非法路径全部干掉了。

这题背后的思想其实可以推广到一类问题：当某个选择会导致状态非法时，直接在递归入口处拦截，而不是生成完再验证。回溯的优势就在这里——你有机会在路径生长的过程中剪枝，代价比事后验证小得多。

4.3 字母大小写全排列：跳过非字母位置

LeetCode 784，给一个字符串如 "a1b2"，大写小写视为不同选择，返回所有大小写组合："a1b2"、"A1b2"、"a1B2"、"A1B2"。

核心点在于：数字字符没有分叉，必须直接进入下一层，只有字母才分大小写两条路。

def letter_case_permutation(s): res = [] def dfs(idx, path): if idx == len(s): res.append(''.join(path)) return ch = s[idx] if ch.isalpha(): path.append(ch.lower()) dfs(idx + 1, path) path.pop() path.append(ch.upper()) dfs(idx + 1, path) path.pop() else: path.append(ch) dfs(idx + 1, path) path.pop() dfs(0, []) return res

这个题其实比前面几道更直观地展示了"决策树"的样子：数字节点只有一个孩子，字母节点有两个孩子。如果字符串很长，字母很多，结果是 2^字母数量 种，这正好提醒你回溯的时间复杂度一定是和"叶子节点数量"相关的。

4.4 目标和：把加减号当成选择

LeetCode 494，给你一个数组 nums 和一个目标 target，你可以在每个数前面加+或-，求有多少种方案让总和等于 target。

这题一眼看过去和"排列组合"没关系，但它本质就是一棵二叉树：每一层决定当前数字取正还是取负。直接回溯：

def find_target_sum_ways(nums, target): n = len(nums) res = 0 def dfs(idx, cur_sum): nonlocal res if idx == n: if cur_sum == target: res += 1 return dfs(idx + 1, cur_sum + nums[idx]) dfs(idx + 1, cur_sum - nums[idx]) dfs(0, 0) return res

这个代码在 nums 长度比较小的时候能过，但 nums 最长能到 30 的话，2^30 种组合会直接超时。所以"目标和"其实更适合用记忆化搜索或者动态规划，这也是下面要单独展开讲的部分。

5. 从递归到搜索的思维跃迁：拿"目标和"说说 DFS + 记忆化

5.1 纯回溯会超时，问题出在哪

以上一节的find_target_sum_ways为例，纯回溯会把所有路径完整遍历一遍。你会发现很多子问题是重复的：比如 nums=[1,1,1,1,1]，处理完前两个数后，无论你是走+1+1还是+1-1-(-1)（这里只是示意），到达的状态(idx=2, cur_sum=某值)可能会被多条不同路径重复到达。每一次重复到达，后面的 2^(n-2) 条路径都会被重新计算一遍，浪费极其严重。

递归树的"重叠子问题"一旦出现，你就该想到记忆化。

5.2 记忆化搜索：在递归树上做缓存

记忆化的写法非常简单：把(idx, cur_sum)这个状态作为 key，把从该状态出发能得到的方案数作为 value，存到缓存里。下次再遇到同样的(idx, cur_sum)，直接返回缓存结果。

Python 里可以用functools.lru_cache，代码改造成这样：

from functools import lru_cache def find_target_sum_ways(nums, target): n = len(nums) @lru_cache(None) def dfs(idx, cur_sum): if idx == n: return 1 if cur_sum == target else 0 return dfs(idx + 1, cur_sum + nums[idx]) + dfs(idx + 1, cur_sum - nums[idx]) return dfs(0, 0)

这里的复杂度从 2^n 降到了 O(n * sum)，因为状态总数就是 idx 的数量乘以 cur_sum 的可能取值范围。我在实际测试里跑过 nums 长度 30、target 任意的场景，纯回溯需要几秒甚至更久，记忆化版本毫秒级返回。

5.3 另一种视角：目标和转化成背包问题

除了记忆化，目标和还有一个非常经典的转化思路，这也是面试中常见的追问点。

设所有取正号的数之和为 P，所有取负号的数绝对值之和为 N，那么有：

• P + N = sum(nums)
• P - N = target

两式相加得：

• P = (sum(nums) + target) / 2

于是问题变成：从 nums 中挑出若干个数，使它们的和等于 P，求有多少种挑法。这就变回了标准的 0/1 背包求方案数问题，或者说变回了"组合总和"问题。

这个转化有两个先决条件：(sum(nums) + target)必须是偶数，否则 P 不是整数，直接返回 0；P 必须是非负数。

写成 DP 就是经典的背包思想，这里我用回溯加记忆化写也能过：

def find_target_sum_ways(nums, target): total = sum(nums) if (total + target) % 2 != 0 or total + target < 0: return 0 P = (total + target) // 2 @lru_cache(None) def dfs(idx, remain): if remain == 0: return 1 if idx == len(nums): return 0 res = dfs(idx + 1, remain) if nums[idx] <= remain: res += dfs(idx + 1, remain - nums[idx]) return res return dfs(0, P)

我个人很推荐把这两种解法都掌握：回溯 + 记忆化是"从搜索的角度理解问题"，转化成背包是"从数学推导的角度理解问题"。面试官如果问你能否优化，你能说出这条转化链，会是非常亮眼的表现。

6. 刷题实战中的小坑：基于我做这 8 道题的真实记录

6.1 复制路径的时机：append 进去的是引用还是快照

这是回溯题最容易踩的坑，没有之一。我在前面已经强调过一次：res.append(path[:])而不是res.append(path)。原因再补一遍：path 是递归过程中反复增删的同一个列表对象，append 进 res 的只是引用。如果不拷贝，等递归返回后 path 被 pop 成空，res 里所有已经存进去的路径就全变成空列表了。

path[:]是浅拷贝，对一维列表足够。如果是二维路径（比如解数独要存棋盘），就得用深拷贝或者逐行拷贝。总之：进结果集合之前，想清楚这个对象后续还会不会被修改。

6.2 剪枝不是可有可无的优化

回溯题不剪枝，在小数据量下和剪枝版本跑不出差异，但一旦数据量上来，差距是数量级的。

我在刷"组合总和"的时候专门对比过：candidates 长度 30、target 较大时，不排序不剪枝的版本递归了 50 多万次，排完序加if candidates[i] > remain: break之后，递归次数降到了几千次。这不是玄学，是排序让"当前选择放不下时后面所有更大值都可以直接放弃"。

剪枝的本质是：利用数据的单调性或题目约束，提前砍掉不可能产生答案的子树。写回溯题时养成一个习惯：每次写完暴力版本，先想想哪些子树是不可能走到答案的，然后加剪枝条件。这个习惯在面试中比正确答案本身更能体现你的工程思维。

6.3 "组合总和 II"和"子集 II"的去重逻辑是同一个

LeetCode 40 组合总和 II（每个数只能用一次）和 LeetCode 90 子集 II（含重复元素求不重复子集），去重代码几乎一模一样，都是排序后：

if i > start and nums[i] == nums[i - 1]: continue

这个模式我强烈建议你单独摘出来背熟，因为它出现的频率太高了。核心思想就是：在有重复元素的组合/子集问题中，保证同一层不枚举相同值。理解了这一句话，这两道题加上全排列 II 的去重，你就全部掌握了。

6.4 时间和空间的复杂度直觉

回溯题的时间复杂度通常等于"决策树节点数"，空间复杂度等于递归深度。给你一个快速估算的参照表：

面试中如果被问复杂度，不要只说"指数级"，最好能说出决策树的层数和分叉数，然后解释为什么是这个量级。能讲清楚复杂度的来源，说明你是真的理解了回溯的树形结构。

6.5 回溯题的变体方向

把这 8 道题刷完之后，你其实已经掌握了回溯的大部分核心套路。后续再遇到以下题目，本质都是同一套思路：

• N 皇后：每层放一个皇后，用列、对角线数组判断冲突。
• 复原 IP 地址：每层切一段，判断是否合法。
• 单词搜索：在二维网格上 DFS 找单词路径，需要 visited 矩阵。
• 分割回文串：每层截取一段，判断是否回文，是则继续。
• 火柴拼正方形 / 划分为 k 个相等的子集：本质是组合问题加状态压缩剪枝。

这些题在模板上没有跳出我前面说的框架，只是在"每层选择什么"上做了更多文章。所以你把基础打牢，后面刷题会越刷越顺。

我在实际刷完这个专题之后最大的体会是：回溯题的代码量都很短，难的是把问题还原成决策树。你问我怎么训练这种还原能力？我的建议是：每道题先不要看题解，自己画出递归树，标清楚每一层的选择列表是什么、结束条件是什么、什么时候需要恢复现场。画个十道八道题之后，再看到"全排列""组合""括号"这些关键词，脑子里自动就会浮现树的形状，代码自然就写出来了。

这套方法比背代码模板有用得多，因为模板解决的是语法层面的问题，而画树解决的是思维层面的问题。后者想通了，前者只是顺手的输出而已。