一句话总结
回溯算法本质是多叉树的深度优先遍历（DFS），核心是回溯三部曲：1）做选择（将当前元素加入路径）→ 2）递归（进入下一层决策树）→ 3）撤销选择（回溯，恢复状态）。模板：for 选择 in 选择列表: 做选择; backtrack(路径, 选择列表); 撤销选择。排列问题用 used 数组去重，组合/子集用 start 索引去重。
初级理解
回溯算法模板
def backtrack(路径, 选择列表):
if 满足结束条件:
result.append(路径[:]) # 注意拷贝！
return
for 选择 in 选择列表:
# 剪枝（可选）
if 不满足条件: continue
做选择（路径.add(选择)）
backtrack(路径, 选择列表)
撤销选择（路径.pop()）
全排列（LeetCode 46）
def permute(nums):
result = []
used = [False] * len(nums)
def backtrack(path):
if len(path) == len(nums):
result.append(path[:])
return
for i in range(len(nums)):
if used[i]:
continue
used[i] = True
path.append(nums[i])
backtrack(path)
path.pop()
used[i] = False
backtrack([])
return result
一句话总结：回溯 = 递归 + 循环 + 撤销；排列用 used 数组，组合/子集用 start 索引。
中级深入
子集（LeetCode 78）
def subsets(nums):
result = []
def backtrack(start, path):
result.append(path[:]) # 每个节点都收集
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1, path) # i+1 保证不重复
path.pop()
backtrack(0, [])
return result
组合总和（LeetCode 39）
# 无重复元素，可重复使用
def combination_sum(candidates, target):
result = []
def backtrack(start, path, remain):
if remain == 0:
result.append(path[:])
return
if remain < 0:
return
for i in range(start, len(candidates)):
path.append(candidates[i])
backtrack(i, path, remain - candidates[i]) # i 不是 i+1（可重复）
path.pop()
backtrack(0, [], target)
return result
全排列 II（含重复元素，LeetCode 47）
def permute_unique(nums):
nums.sort() # 排序让相同元素相邻
result = []
used = [False] * len(nums)
def backtrack(path):
if len(path) == len(nums):
result.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])
backtrack(path)
path.pop()
used[i] = False
backtrack([])
return result
中级要点：子集/组合用 start 索引避免重复；含重复元素先排序，用 used 或 start 去重。
高级拓展
N 皇后（LeetCode 51）
def solve_n_queens(n):
result = []
board = [['.'] * n for _ in range(n)]
cols = set() # 列
diag1 = set() # 主对角线（row-col）
diag2 = set() # 副对角线（row+col）
def backtrack(row):
if row == n:
result.append([''.join(r) for r in board])
return
for col in range(n):
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)
backtrack(row + 1)
board[row][col] = '.'
cols.remove(col)
diag1.remove(row - col)
diag2.remove(row + col)
backtrack(0)
return result
回溯 vs 动态规划
| 维度 | 回溯 | 动态规划 |
|---|---|---|
| 问题类型 | 求所有解（排列/组合/子集） | 求最优解（最大/最小/计数） |
| 核心操作 | 选择 → 递归 → 撤销 | 状态转移方程 |
| 时间复杂度 | 通常指数级 | 通常多项式级 |
| 优化手段 | 剪枝 | 记忆化搜索、状态压缩 |
实战场景
场景：电话号码的字母组合（LeetCode 17）
def letter_combinations(digits):
if not digits: return []
phone = {
'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
'6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
}
result = []
def backtrack(index, path):
if index == len(digits):
result.append(''.join(path))
return
for ch in phone[digits[index]]:
path.append(ch)
backtrack(index + 1, path)
path.pop()
backtrack(0, [])
return result
面试模拟
面试官：回溯算法的核心框架是什么？
你：回溯三部曲：1）做选择（加入路径）；2）递归进入下一层；3）撤销选择（回溯）。本质是多叉树的 DFS。排列问题用 used 数组标记已选元素，组合/子集用 start 索引保证不重复选取。含重复元素时先排序，再通过 used 或 start 去重。
面试官：全排列有重复元素怎么去重？
你：先排序让相同元素相邻。在回溯的 for 循环中，如果 nums[i] == nums[i-1] 且 !used[i-1]（前一个相同元素没被使用），说明是同一层的重复选择，跳过。注意是 !used[i-1] 而不是 used[i-1]，前者是树层去重，后者是树枝去重。