题目描述
思路解析动画文字版
想象你在一层层做决定：每层挑一个还没用过的数放进路径 path；path 凑满 3 个就记下来；然后撤销刚才的选择，回到上一层换一个数继续。
开始：路径 path 一开始是空的，三个数都没用过，结果 res 也是空。
第1层 · 选 1：第一层先选 1：标记 1 已用，放进 path。path = [1]。
第2层 · 想选 1？：进第二层，枚举从头开始：想选 1？它已经在路径里了，used[0]=True，打叉跳过，看下一个。这就是代码里 if used[i]: continue 那一行在画面上的样子。
第2层 · 选 2：还是这一层，往后继续枚举：跳过 1 之后轮到 2，选它。path = [1, 2]。
第3层 · 选 3：第三层只剩 3，选它。path = [1, 2, 3]，凑满 3 个了！
收集：path 长度等于 3，记下这个排列 [1,2,3]。然后开始往回退（回溯）。
撤销 3：撤销刚才的 3：把它移出 path、标记为没用过。回到第二层，可这层除了 3 没别的可选了，继续往上退。
撤销 2：撤销 2，回到 path = [1]。第一层选过 1 后，第二层还能换成 3 试试。
第2层 · 改选 3：这次第二层选 3。path = [1, 3]。
第3层 · 选 2 · 收集：第三层只剩 2，凑满 [1, 3, 2]，记下来。以 1 开头的排列全找完了。
一路撤销回开头：继续撤销，一直退回 path 为空。现在换第一个数，不选 1 了。
换开头 · 选 2：第一层改选 2——注意 used 只有 2 亮着，1 和 3 都被撤销复位了，所以它俩在下面又能被选。撤销谁、什么时候撤销正是回溯能换分支的关键。1 开头那条已逐帧讲透，这条同构，只看结果。
2 开头 · 两种排列：2 之后只剩 1、3：先 1 后 3 得 [2,1,3]；撤销到 [2]、第二层换 3，再得 [2,3,1]。和 1 开头一模一样的「选→递归→收集→撤销」，不再逐帧重画。
撤销回开头 · 选 3：2 开头穷举完，撤到 used 全空，第一层选最后一个 3。剩下 1、2 接着排。
3 开头 · 两种排列：同样的套路：3 后选 1 再选 2 得 [3,1,2]；撤回 [3] 换 2 得 [3,2,1]。六种全部到齐。
全部找齐：撤销到底、path 清空，6 种排列不重不漏全部找齐。这就是回溯的威力：系统地穷举所有可能。
它没有任何数学技巧，就是把每条路都走一遍；唯一的巧妙是「撤销」让一份 path 反复复用，省下重新构造的成本。子集、组合、N 皇后……都是它的变体。
雷区实演 · 忘了 pop：亲眼看一次塌方：收完 [1,2,3] 后如果漏了 pop，path 还撑着 3 个数退不回去，第二种排列 [1,3,2] 根本没机会被装进 path——res 永远只收得到这一份。这就是上一帧雷区、也是下面小测 2 的考点。
迁移阶梯：把这题练到能复述后，再去同类题里迁移：先复用状态定义，再调整边界条件。
边界三连：边界三连：极端输入先过一遍。
几个高频追问，记住答法。
参考代码
class Solution: def permute(self, nums): ans = [] used = [False] * len(nums) def backtrack(path): if len(path) == len(nums): ans.append(path[:]) return for i, x in enumerate(nums): if used[i]: continue used[i] = True path.append(x) backtrack(path) path.pop() used[i] = False backtrack([]) return ans复杂度
- 时间复杂度：O(n × n!)，n! 种排列，每种花 O(n) 拷贝
- 空间复杂度：O(n)，递归深度 + path
可套用的代码模板
把它当骨架背下来：结束就收集（记得拷贝）→ 枚举选择 → 做选择 → 递归 → 撤销。子集/组合/排列只改「结束条件」和「选择列表」，骨架一字不动。
def backtrack(path): if 满足结束条件: res.append(path[:]) # 注意 [:] 拷贝 return for 选择 in 选择列表: if 不能选: continue 做选择(path) # append + used=True backtrack(path) 撤销选择(path) # pop + used=False易错点
面试追问把动画讲成自己的话
追问排列为什么用 used 而不是 start？
追问有重复元素(LC47)怎么去重？
追问复杂度？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
子集 II
LeetCode 90 · 中等 · 沿着 回溯 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题