result = []def backtrack(path, choices): # 结束条件 if "满足条件": result.append(path[:]) # 深拷贝，非常重要！ return for choice in choices: # 做选择 path.append(choice) # 进入下一层决策树 backtrack(path, new_choices) # 撤销选择 path.pop()
三个关键点
关键点
说明
常见错误
深拷贝
result.append(path[:]) 而非 path
直接 append(path) 会导致 result 中的值随 path 变化
撤销操作
递归返回后必须把状态还原
忘记 pop 或忘记还原 visited 标记
剪枝
在递归前跳过无效的选择
漏掉剪枝条件导致大量无用计算
三、核心变体
变体 1：全排列（用 visited 排除已选）
def permute(nums): res = [] used = [False] * len(nums) def backtrack(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]) backtrack(path) path.pop() used[i] = False backtrack([]) return res
变体 2：子集（用 start 控制不回头）
def subsets(nums): res = [] def backtrack(start, path): res.append(path[:]) # 每个节点都加入结果 for i in range(start, len(nums)): path.append(nums[i]) backtrack(i + 1, path) path.pop() backtrack(0, []) return res
变体 3：组合总和（可重复选 + 剪枝）
def combination_sum(candidates, target): res = [] candidates.sort() # 排序便于剪枝 def backtrack(start, path, remaining): if remaining == 0: res.append(path[:]) return for i in range(start, len(candidates)): if candidates[i] > remaining: # 剪枝 break path.append(candidates[i]) backtrack(i, path, remaining - candidates[i]) # 可重复选，start 传 i path.pop() backtrack(0, [], target) return res
变体 4：单词搜索（网格上的回溯）
def exist(board, word): m, n = len(board), len(board[0]) def backtrack(i, j, k): if k == len(word): return True if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != word[k]: return False # 标记已访问 temp, board[i][j] = board[i][j], '#' res = (backtrack(i+1, j, k+1) or backtrack(i-1, j, k+1) or backtrack(i, j+1, k+1) or backtrack(i, j-1, k+1)) board[i][j] = temp # 撤销标记 return res for i in range(m): for j in range(n): if backtrack(i, j, 0): return True return False
变体 5：N 皇后（经典棋盘问题）
def solve_n_queens(n): res = [] # 列、主对角线、副对角线的占用标记 cols = set() diag1 = set() # 主对角线：row - col 为常数 diag2 = set() # 副对角线：row + col 为常数 def backtrack(row, path): if row == n: res.append([''.join(row) for row in path]) return for col in range(n): if col in cols or (row - col) in diag1 or (row + col) in diag2: continue # 做选择 cols.add(col) diag1.add(row - col) diag2.add(row + col) path.append(['Q' if c == col else '.' for c in range(n)]) backtrack(row + 1, path) # 撤销选择 path.pop() cols.remove(col) diag1.remove(row - col) diag2.remove(row + col) backtrack(0, []) return res
四、排列 vs 组合 vs 子集
问题
使用方式
去重方式
结果数量
排列
每次从所有元素中选
visited 标记已选
n!
组合
每次从 start 之后选
start 参数控制
C(n,k)
子集
每次从 start 之后选
start 参数控制
2^n
含重复元素时的去重技巧（排序+跳过同层重复）：
# 以全排列去重为例nums.sort()for i in range(len(nums)): if used[i] or (i > 0 and nums[i] == nums[i-1] and not used[i-1]): continue