一句话总结
回溯 = 穷举 + 撤销。它在一棵"决策树"上做深度优先遍历：每到一个节点就做一次选择（做选择 → 递归 → 撤销选择），走到叶子就得到一个解。所谓"回溯"，就是递归返回后把刚才的选择抹掉，回到分叉口去试下一条路。
🌲
决策树
每一层是一次选择，每个叶子是一个完整答案。回溯就是遍历这棵树。
✅
路径 path
记录"已经做出的选择"，到叶子时它就是答案的一部分。
📋
选择列表
当前这一步还能选什么，通常用 start 下标或 used 数组控制。
✂️
剪枝
提前排除必不可能的分支，是回溯从超时到通过的关键。
一、通用框架：三步走
1.1 模板代码
def backtrack(路径, 选择列表):
if 满足结束条件: # ① 终止：走到叶子
result.append(路径[:]) # 注意要拷贝！
return
for 选择 in 选择列表: # ② 遍历所有可选分支
if 该选择不合法: # 剪枝（可选）
continue
做选择(路径.add(选择)) # ③ 前序：做选择
backtrack(路径, 新选择列表) # 递归进入下一层
撤销选择(路径.pop()) # ④ 后序：撤销，回到分叉口
💡 为什么必须"撤销"？因为
path 是一个被所有分支共享的对象。不撤销的话，试完第一条路回到分叉口时，path 里还残留着上一个分支的数据，下一条分支就会带着脏数据走下去。
1.2 决策树可视化：全排列 [1,2,3]
二、四大经典题型
2.1 全排列（LeetCode 46）：元素可复用性用 used 数组控制
def permute(nums):
res, path = [], []
used = [False] * len(nums)
def dfs():
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.pop() # 撤销
used[i] = False # 撤销
dfs()
return res
2.2 子集（LeetCode 78）：每个节点都是答案
def subsets(nums):
res, path = [], []
def dfs(start):
res.append(path[:]) # ★ 每个节点都要收集（不是只在叶子）
for i in range(start, len(nums)):
path.append(nums[i])
dfs(i + 1) # 从 i+1 开始 → 避免重复、天然去重
path.pop()
dfs(0)
return res
# 结果：[[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]] —— 共 2^n 个
2.3 组合（LeetCode 77）：多了个数限制
def combine(n, k):
res, path = [], []
def dfs(start):
if len(path) == k: # 选够 k 个 → 收集
res.append(path[:])
return
# 剪枝：剩余可选数量 n - start + 1 要够填满 k - len(path) 个位置
for i in range(start, n - (k - len(path)) + 2):
path.append(i)
dfs(i + 1)
path.pop()
dfs(1)
return res
2.4 N 皇后（LeetCode 51）：二维约束 + 剪枝
def solveNQueens(n):
res = []
board = [['.'] * n for _ in range(n)]
cols, diag1, diag2 = set(), set(), set() # 列、主对角、副对角
def dfs(row):
if row == n: # 所有行都放好了
res.append([''.join(r) for r in board])
return
for col in range(n):
# 技巧：同一主对角线上 row-col 恒定；同一副对角线上 row+col 恒定
if col in cols or (row - col) in diag1 or (row + col) in diag2:
continue # 冲突 → 剪枝，不试这条分支
board[row][col] = 'Q'
cols.add(col); diag1.add(row - col); diag2.add(row + col)
dfs(row + 1) # 进入下一行
board[row][col] = '.'
cols.remove(col); diag1.remove(row - col); diag2.remove(row + col)
dfs(0)
return res
三、剪枝：让回溯从超时到通过
3.1 两类剪枝
| 类型 | 做法 | 例子 |
|---|---|---|
| 可行性剪枝 | 当前分支已违反约束，直接 return | N 皇后的列/对角线冲突、组合总和超过 target |
| 重复性剪枝 | 同一层遇到相同元素只取第一个 | 40 组合总和 II：if i > start and nums[i] == nums[i-1]: continue |
| 上下界剪枝 | 剩余元素不够填满/已超过，直接退出循环 | 77 组合：for i in range(start, n - need + 2) |
| 记忆化（最优性剪枝） | 记录已算过的状态 | 括号生成中记录已生成的串 |
3.2 去重剪枝图解（含重复元素的组合）
核心口诀：排序 + 同层跳过。先对数组排序，然后在
for 循环里加一句——如果当前元素和"同一层的上一个元素"相同，就跳过。注意必须是同一层（i > start），不能跨层比较，否则会漏掉合法解。
# 40. 组合总和 II：candidates 有重复，每个数字只能用一次
def combinationSum2(candidates, target):
candidates.sort() # ① 必须先排序，让相同元素相邻
res, path = [], []
def dfs(start, remain):
if remain == 0:
res.append(path[:]); return
for i in range(start, len(candidates)):
if i > start and candidates[i] == candidates[i-1]:
continue # ② 同层重复 → 跳过，避免重复解
if candidates[i] > remain:
break # ③ 已排序 → 后面更大，直接剪掉
path.append(candidates[i])
dfs(i + 1, remain - candidates[i])
path.pop()
dfs(0, target)
return res
四、复杂度与题型对照
| 题型 | 答案数量 | 时间复杂度 | 空间复杂度 | 关键约束 |
|---|---|---|---|---|
| 子集 78 | 2ⁿ | O(n × 2ⁿ) | O(n) | start 递增，每个节点都收集 |
| 组合 77 | C(n,k) | O(k × C(n,k)) | O(k) | start 递增 + 个数上限 |
| 全排列 46 | n! | O(n × n!) | O(n) | used 数组，可任意顺序选 |
| N 皇后 51 | 远小于 n! | O(n!) | O(n) | 行 + 列 + 双对角线集合剪枝 |
| 括号生成 22 | 卡特兰数 | O(4ⁿ/√n) | O(n) | 左括号数 ≥ 右括号数 |
⚠️ 面试高频错误：
①
② 撤销操作漏写（只 pop 不还原 used/集合）→ 状态污染；
③ 去重剪枝时用了
④ 在循环里
①
res.append(path) 忘记加 [:] → 所有答案都指向同一个 path，最后全是空列表；② 撤销操作漏写（只 pop 不还原 used/集合）→ 状态污染；
③ 去重剪枝时用了
i > 0 而非 i > start → 跨层误杀，漏解；④ 在循环里
break 而非 continue 前没先排序 → 提前截断合法分支。
一句话心法：回溯题先画决策树——问自己三件事：① 每层"选什么"（全排列选元素、子集选要不要、N 皇后选列）；② 什么条件下算一个答案（到叶子？还是每个节点都是？）；③ 怎么避免重复和无效分支（start 递增 / used 数组 / 排序跳过 / 上下界剪枝）。