引言 (Introduction)
回溯算法（Backtracking）是暴力搜索中最核心的方法论。面对一个解空间呈指数级的问题，回溯通过"试探—撤回—重试"的策略系统性地枚举所有候选解。在 LeetCode 上，涉及回溯的题目超过 100 道，涵盖子集、排列、组合、分割、棋盘、网格搜索等众多变体。
本文是本系列第一篇，聚焦于回溯算法的通用框架与子集生成问题。我们将从决策树的视角建立直觉，提炼出适用于绝大多数回溯题目的代码模板，再通过三道子集问题逐层深入。
首先，我们统一定义回溯算法的标准函数签名与数据结构：
from typing import List
def dfs(path: List[int], choices: List[int], start: int) -> None:
"""回溯算法的通用入口：path 记录当前路径，start 控制选择范围"""
...
1. 决策树视角下的回溯
1.1 从全枚举到回溯
任何一个搜索问题都可以看作在一棵决策树（Decision Tree）上行走。决策树的每个节点代表一次"选择"，每条从根到叶子的路径代表一个完整的候选解。
以 nums = [1, 2, 3] 的子集生成为例，决策树如下：
[]
/ \
选1: [1] 不选1: []
/ \ / \
选2: [1,2] 不选2: [1] 选2: [2] 不选2: []
/ \ / \ / \ / \
选3: ... ... ... ... ... ... ... ...
每个元素面临"选或不选"的二元决策，$n$ 个元素产生 $2^n$ 条路径，恰好对应 $2^n$ 个子集。
回溯的核心思想是：沿一条分支走到叶节点，记录结果；然后撤销最后一步选择（回溯），尝试另一条分支。这种"进—退—进"的节奏是回溯算法的唯一本质特征。
1.2 回溯与 DFS 的关系
回溯是 DFS 在状态空间上的应用，但两者有一个关键区别：
- DFS 的目标是遍历所有节点，每个节点只访问一次。
- 回溯的目标是遍历所有路径，每个节点可能被多次访问（从不同路径到达）。
换言之，回溯 = DFS + 状态撤销（path.pop()）。这行不起眼的 pop() 才是回溯的灵魂——没有它，你只是在做普通的递归遍历。
2. 通用回溯模板
2.1 模板代码
绝大多数回溯问题都可以套用以下模板：
from typing import List
class BacktrackTemplate:
"""回溯算法通用模板"""
def backtrack(self, nums: List[int]) -> List[List[int]]:
res: List[List[int]] = [] # 结果集
path: List[int] = [] # 当前路径（状态）
def dfs(start: int) -> None:
# ---- 1. 记录答案（视问题决定是否每条路径都记录）----
res.append(path[:]) # 拷贝当前路径
# ---- 2. 尝试每一个可选项 ----
for i in range(start, len(nums)):
# ---- 2a. 剪枝（可选）----
# if should_skip(i): continue
# ---- 2b. 做选择 ----
path.append(nums[i])
# ---- 2c. 递归进入下一层 ----
# 参数 i+1 确保每个元素只被选一次（不可重复使用）
dfs(i + 1)
# ---- 2d. 撤销选择（回溯！）----
path.pop()
dfs(0)
return res
四个核心要素：
path（路径）：已做出的选择序列，表示当前搜索所处的状态。choices（选择列表）：当前状态下还可以选择的元素。在模板中由start参数隐式控制——nums[start:]就是当前可选集合。res（结果集）：收集所有合法路径的快照。- 剪枝条件：提前终止不可能产生合法解的分支，是回溯算法性能优化的核心手段。
2.2 子集问题的"选与不选"范式 vs “逐步添加"范式
子集生成有两种等价写法，理解它们的区别有助于后续理解排列、组合等问题：
范式 A：选 / 不选（二叉树式决策）
def dfs(i: int) -> None:
if i == len(nums):
res.append(path[:])
return
# 不选 nums[i]
dfs(i + 1)
# 选 nums[i]
path.append(nums[i])
dfs(i + 1)
path.pop()
范式 B：逐步添加（for 循环式决策）
def dfs(start: int) -> None:
res.append(path[:])
for i in range(start, len(nums)):
path.append(nums[i])
dfs(i + 1)
path.pop()
两种写法的时间复杂度均为 $O(N \cdot 2^N)$。范式 B 更直观且易于扩展（加一个 start 参数即可转化为组合问题），本系列后续均采用此范式。
2.3 复杂度分析
回溯算法的复杂度分析遵循一个核心公式：
$$T(n) = O(\text{叶节点数} \times \text{单条路径的拷贝成本})$$对于子集问题：
-
叶节点数（解的数量）：$2^N$（$N$ 个元素，每个可选或不选）
-
路径拷贝成本：
path[:]复制一个长度至多为 $N$ 的列表，$O(N)$ -
总时间复杂度：$O(N \cdot 2^N)$
-
空间复杂度：递归调用栈深度最大为 $O(N)$，不考虑结果存储。
为什么回溯跑得通但看上去复杂度是"指数级”？ 因为问题的输出本身就是指数级大小。$N$ 个元素的子集共有 $2^N$ 个，任何算法都必须输出 $2^N$ 个结果。回溯的复杂度是 output-sensitive——它只花时间在"生成答案"这件事上，不做多余的无效搜索（除非剪枝不力）。
3. LeetCode 78：子集（Subsets）
题目：给定一个不含重复元素的整数数组 nums，返回其所有可能的子集（幂集）。解集不能包含重复的子集。
3.1 解法：基础回溯
直接套用模板，无需任何剪枝：
from typing import List
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res: List[List[int]] = []
path: List[int] = []
def dfs(start: int) -> None:
# 每个节点（无论是否为叶节点）都对应一个子集
res.append(path[:])
for i in range(start, len(nums)):
path.append(nums[i]) # 选择
dfs(i + 1) # 递归
path.pop() # 回溯
dfs(0)
return res
决策树示例（nums = [1, 2, 3]）：
[] ← 加入 res
/ | \
[1] [2] [3] ← 各自加入 res
/ \ |
[1,2] [1,3] [2,3] ← 各自加入 res
/
[1,2,3] ← 加入 res
共 $2^3 = 8$ 个子集全部收集完毕。关键观察：start 参数只允许向后选择，这天然避免了出现 [2, 1] 这样的重复排列子集（因为子集本身是无序的）。
3.2 迭代解法（位运算）
作为补充，子集问题还有一种巧妙的位运算解法。因为每个元素对应"选"或"不选"两种状态，可以用一个二进制数 $[0, 2^N - 1]$ 唯一标识一个子集：
def subsets_bitmask(nums: List[int]) -> List[List[int]]:
"""位运算枚举子集"""
n = len(nums)
res: List[List[int]] = []
for mask in range(1 << n): # 0 到 2^n - 1
subset: List[int] = []
for i in range(n):
if mask >> i & 1: # 第 i 位是 1 → 选 nums[i]
subset.append(nums[i])
res.append(subset)
return res
时间复杂度相同（$O(N \cdot 2^N)$），但在实际工程中位运算通常更快，且不依赖递归栈。
4. LeetCode 90：子集 II（含重复元素）
题目：给定一个可能包含重复元素的整数数组 nums，返回其所有可能的子集。解集不能包含重复的子集。
4.1 难点：如何避免重复子集
当 nums 中有重复元素时，决策树的不同分支可能生成相同的子集。例如 nums = [1, 2, 2]：选择第一个 2 和不选择第二个 2 的部分路径会收敛到同一个状态。
核心策略：排序 + 横向剪枝。
- 排序：让相同元素相邻，这是去重的前提。
- 横向剪枝：在
for循环的同一层，如果当前元素等于前一个元素，且前一个元素没有被选入当前路径，则跳过当前元素。
“前一个元素未被选入"的含义是 i > start and nums[i] == nums[i - 1]——因为 start 是当前层的起始索引，若 i > start 说明 nums[i-1] 是同一层已经尝试过的兄弟节点：
[ ]
/ | \
1 2 2(×) ← 横向：同一层出现第二个2，跳过
/ \ / \ / \
2 2 2 x x x
/ / /
2 x x
图中 (×) 标记的分支会被剪枝。左侧第一个 2 已经生成了所有包含 “至少一个 2” 的子集，右侧第二个 2 再做一遍会产生完全重复的结果。
4.2 完整代码
from typing import List
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
nums.sort() # 关键：排序使重复元素相邻
res: List[List[int]] = []
path: List[int] = []
def dfs(start: int) -> None:
res.append(path[:])
for i in range(start, len(nums)):
# 横向剪枝：同一层跳过重复元素
if i > start and nums[i] == nums[i - 1]:
continue
path.append(nums[i])
dfs(i + 1)
path.pop()
dfs(0)
return res
剪枝条件 i > start and nums[i] == nums[i - 1] 的精确含义：
i > start：nums[i - 1]是同一层已经尝试过的元素（而非上一层递归选入的）。nums[i] == nums[i - 1]：当前元素与刚才的同层兄弟相同，其下所有分支都已经被兄弟探索过了。
一个常见错误是把
i > start写成i > 0。i > 0会导致纵向也去重——禁止了在路径中选择第二个重复元素（如[2, 2]），这是错误的。
i > start是横向剪枝，used[i-1] == False（排列问题中会用到）本质相同但引入了额外数组。理解两者的等价性是进阶关键。
5. LeetCode 1863：子集异或和
题目：给定一个数组 nums，求出所有子集的异或（XOR）总和。其中，一个子集的异或总和定义为该子集中所有元素的按位异或结果。
这道题是子集生成的应用——你不需要任何新算法，只需在生成每个子集的同时计算其 XOR 值即可。
5.1 解法：回溯 + 实时异或
from typing import List
class Solution:
def subsetXORSum(self, nums: List[int]) -> int:
total: int = 0
def dfs(start: int, xor: int) -> None:
nonlocal total
total += xor # 累加当前子集的 XOR 值
for i in range(start, len(nums)):
dfs(i + 1, xor ^ nums[i]) # 选择 nums[i]，更新 XOR
dfs(0, 0)
return total
技巧：xor 作为参数传入，省去了维护 path 列表的开销。异或运算的特性（$a \oplus a = 0$）意味着不需要显式撤销——递归返回后，上层调用者手中的 xor 变量天然保持着进入递归前的值（参数传递是值拷贝）。
5.2 数学优化（非必需，但有趣）
这道题还有一个 $O(N)$ 的数学解法：按位统计。对于第 $k$ 个二进制位，若 nums 中至少有一个元素的第 $k$ 位是 $1$，那么在所有子集 XOR 和中，该位贡献的次数为 $2^{N-1}$ 次。
def subsetXORSum_math(nums: List[int]) -> int:
"""按位统计法：O(N) 时间"""
or_sum = 0
for x in nums:
or_sum |= x
return or_sum * (1 << (len(nums) - 1))
这体现了回溯算法不一定总是最优解——但回溯永远是最通用的解。当你找不到巧妙的数学性质时，回溯模板永远是可靠的备选。
6. 回溯模板的变体维度
在继续深入学习后续问题之前，我们先建立一张"回溯模板参数调参表”，把后续所有变体统一在这个框架下理解：
| 维度 | 子集问题 | 组合问题 | 排列问题 |
|---|---|---|---|
| 记录时机 | 每个节点都记录 | 叶节点记录（len(path) == k） |
叶节点记录 |
start 参数 |
i + 1（不可重复） |
i + 1（不可重复） |
不需要（每次都从 0 开始） |
| 去重方式 | 排序 + i > start |
排序 + i > start |
排序 + used 数组 |
| 剪枝方向 | 横向（同层去重） | 横向 + 纵向（长度/总和） | 纵向（used 标记已选） |
这张表将在后续三篇文章中被反复验证。理解子集模板相当于拿到了理解所有回溯问题的"钥匙"——后续的排列、组合、分割、棋盘问题，都是在这把钥匙上雕刻更精细的齿痕。
结论 (Conclusion)
本文从决策树的视角出发，建立了回溯算法的通用模板，并通过三道子集问题（LeetCode 78、90、1863）完成了从"套用模板"到"理解剪枝"的认知跃迁。核心要点如下：
- 回溯 = DFS + 状态撤销。
path.pop()是灵魂。 - 通用模板：
for i in range(start, n) { 选择; 递归; 撤销 }。 - 横向剪枝：
i > start and nums[i] == nums[i-1]避免了同层兄弟导致的重复。 - 复杂度：$O(N \cdot 2^N)$ 这个形式不意味着算法"慢"——输出本身就是指数级大小。
下一篇我们将把 start 参数的语义推向极致，探讨排列与组合问题的区别——这是回溯算法中变体最丰富、剪枝空间最大的领域。