核心要点
框架：在每层做一个选择 → 递归进入下一层 → 撤销选择恢复现场，遍历决策树
关键：用 path 记录路径、used/start 控制可选范围，到达终止条件时收集结果
剪枝：提前排除不可能的分支（如组合用 start 去重、N 皇后判断列与对角线冲突）降低复杂度
标准回答
回溯是一种系统枚举所有候选解的深度优先搜索，核心三步是「做选择—递归—撤销选择」，本质是在一棵决策树上遍历。模板里用 path 保存当前路径，到达终止条件就把 path 的副本加入结果；遍历完一个分支后必须撤销刚才的选择（回到上一状态），才能正确探索兄弟分支。剪枝是性能关键：组合问题用 start 避免重复选取，N 皇后用集合判断列和两条对角线是否冲突。下面给出全排列的标准实现：
python
def permute(nums):
# 全排列：每层从未使用的数里选一个
res = []
path = []
used = [False] * len(nums)
def backtrack():
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.pop() # 撤销选择，恢复现场
used[i] = False
backtrack()
return res
if __name__ == '__main__':
print(permute([1, 2, 3]))
# [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]常见误区
⚠️ 常见踩坑
收集结果时必须用 path[:] 存副本，直接存 path 会因后续 pop 被清空；忘记撤销选择会导致状态污染、结果错误。
追问
追问 1：全排列的时间复杂度是多少？
共有 n! 个排列，每个长度 n，生成与拷贝代价 O(n)，故时间约 O(n × n!)，空间 O(n)（递归深度与 path/used）。这是搜索类问题的固有规模，剪枝只能减小常数而不改变量级。
追问 2：组合问题（如从 n 选 k）如何避免重复？
引入 start 参数，每层只从 start 及之后的元素中选取，递归时传入 i+1，这样保证组合内元素下标递增、不会出现 [1,2] 和 [2,1] 这种重复组合。还可加 len(path)+剩余元素 < k 的剪枝提前返回。
延伸学习
与本题相关的知识库文章、术语、工具与行业资讯。