题目描述
思路解析
一句话答案：LeetCode 46 全排列的标准解法是回溯（带撤销的 DFS）：用 path 记录当前排好的前缀，用 used 数组标记哪些数已经在路径里，每一层从没用过的数中选一个放进 path 递归下去，凑满 n 个就收集一份拷贝，返回时弹出并复位标记，换下一个数继续。时间 O(n·n!)，空间 O(n)。
全排列这道题真正在问什么
给一个不含重复数字的数组 nums，返回它所有可能的排列，顺序不限。比如 [1, 2, 3] 有 6 种排法。这题要的不是「有几种」，而是把每种排列本身都列出来——答案规模就是 n! 个，绕不开逐一生成，真正的考点是：怎么生成得不重、不漏、代码还能对任意 n 通用。
为什么全排列要用回溯而不是嵌套循环
最直觉的想法是写循环：第一层挑第 1 个位置放谁，第二层挑第 2 个位置，一直嵌套下去。三个数写三层循环还行，可 n 是变量，循环层数没法在代码里写死——这条路在结构上就走不通。
关键观察是：生成一个排列，本质是逐位做决策。第 1 位可以放任何一个数，第 2 位可以放任何一个还没用过的数，以此类推。所有决策展开是一棵树，叶子就是完整排列。要把叶子一个不漏地收齐，自然的做法就是深度优先搜索这棵决策树；而「不定层数的嵌套循环」正好被递归取代——每递归一层等于多套一层循环。这种一边做选择、探完再撤销选择的 DFS，就是回溯算法。
path 和 used 数组各自维护什么不变量
path 存当前已经排好的前缀，used 数组标记每个数是否已被 path 占用。两者始终同步：任何时刻 used 里为真的数，恰好就是 path 里的那些数。有了这条不变量，每层的候选就很干净——把 nums 扫一遍，跳过 used 为真的，剩下的都能放进当前位。当 path 长度等于 nums 长度，说明每个数各就各位，收集一份进结果。
很多人会把组合题的「起点 start」套过来做去重，这在排列题里是错的：start 只允许往后选，可排列恰恰要求前面选过位置的数之后还能出现在别的位置上。排列的去重维度是「这个数用没用过」，所以必须用 used 标记，而不是限制下标范围。
为什么递归回来必须撤销选择
整棵决策树共用同一份 path 和 used，这是回溯省空间的精髓，也是它最容易错的地方。递归返回意味着「以刚才那个选择开头的分支已经探完」，此时必须把这个数从 path 弹出、used 复位，让本层状态恢复到做选择之前，才能公平地尝试下一个候选。不撤销的话，path 会越堆越长、used 永远占着，后面的分支全部建立在脏状态上。
还有一个隐蔽的坑：收集答案时要写 res.append(path[:])，存 path 的拷贝而不是 path 本身。因为 path 之后还会被反复修改，存引用会让结果里所有排列最终指向同一个被清空的列表。
复杂度怎么算，重复数字怎么办
时间 O(n·n!)：决策树有 n! 个叶子，每到一个叶子要把长度为 n 的 path 拷贝进结果，这一步就贡献了主要成本。空间 O(n)：递归深度、path、used 都只随 n 线性增长，结果本身不计。
本题保证数字互不相同；如果数组含重复数字（LeetCode 47 全排列 II），要先排序让相同的数相邻，再在每层循环里跳过「同层刚试过的相同值」，否则会生成重复排列。另一种省掉 used 的写法是交换法：把当前位与后面每个数交换后递归、再换回来，两种写法等价，used 法更直观。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这套「选一个没用过的 → 递归 → 撤销再换下一个」，下面整棵决策树都在重复它。
准备 · 空路径：开局：路径 path 是空的，3 个数都还没用过（亮着=可选）。我们从第一位开始，依次尝试把每个数放进来。
选 1 · 第 1 位：第 1 位：从没用过的数里选 1 放进路径，标记它已用（变灰）。当前 path = [1]，继续往下填。
选 2 · 第 2 位：第 2 位：从没用过的数里选 2 放进路径，标记它已用（变灰）。当前 path = [1, 2]，继续往下填。
选 3 · 第 3 位：第 3 位：从没用过的数里选 3 放进路径，标记它已用（变灰）。当前 path = [1, 2, 3]，继续往下填。
凑齐排列 · [1,2,3]：path 长度到 3 了，凑齐一个完整排列 [1, 2, 3]！记进结果 res（现在有 1 个）。接着回溯，退回上一层换别的数。
回溯 · 撤销 3：这条分支探完了，撤销选择：把 3 从路径弹出、改回「没用过」（重新亮起）。回到这一层，准备试下一个数。
回溯 · 撤销 2：这条分支探完了，撤销选择：把 2 从路径弹出、改回「没用过」（重新亮起）。回到这一层，准备试下一个数。
选 3 · 第 2 位：第 2 位：从没用过的数里选 3 放进路径，标记它已用（变灰）。当前 path = [1, 3]，继续往下填。
选 2 · 第 3 位：第 3 位：从没用过的数里选 2 放进路径，标记它已用（变灰）。当前 path = [1, 3, 2]，继续往下填。
凑齐排列 · [1,3,2]：path 长度到 3 了，凑齐一个完整排列 [1, 3, 2]！记进结果 res（现在有 2 个）。接着回溯，退回上一层换别的数。
回溯 · 撤销 2：这条分支探完了，撤销选择：把 2 从路径弹出、改回「没用过」（重新亮起）。回到这一层，准备试下一个数。
回溯 · 撤销 3：这条分支探完了，撤销选择：把 3 从路径弹出、改回「没用过」（重新亮起）。回到这一层，准备试下一个数。
回溯 · 撤销 1：这条分支探完了，撤销选择：把 1 从路径弹出、改回「没用过」（重新亮起）。回到这一层，准备试下一个数。
选 2 · 第 1 位：第 1 位：从没用过的数里选 2 放进路径，标记它已用（变灰）。当前 path = [2]，继续往下填。
选 1 · 第 2 位：第 2 位：从没用过的数里选 1 放进路径，标记它已用（变灰）。当前 path = [2, 1]，继续往下填。
选 3 · 第 3 位：第 3 位：从没用过的数里选 3 放进路径，标记它已用（变灰）。当前 path = [2, 1, 3]，继续往下填。
凑齐排列 · [2,1,3]：path 长度到 3 了，凑齐一个完整排列 [2, 1, 3]！记进结果 res（现在有 3 个）。接着回溯，退回上一层换别的数。
回溯 · 撤销 3：这条分支探完了，撤销选择：把 3 从路径弹出、改回「没用过」（重新亮起）。回到这一层，准备试下一个数。
回溯 · 撤销 1：这条分支探完了，撤销选择：把 1 从路径弹出、改回「没用过」（重新亮起）。回到这一层，准备试下一个数。
选 3 · 第 2 位：第 2 位：从没用过的数里选 3 放进路径，标记它已用（变灰）。当前 path = [2, 3]，继续往下填。
选 1 · 第 3 位：第 3 位：从没用过的数里选 1 放进路径，标记它已用（变灰）。当前 path = [2, 3, 1]，继续往下填。
凑齐排列 · [2,3,1]：path 长度到 3 了，凑齐一个完整排列 [2, 3, 1]！记进结果 res（现在有 4 个）。接着回溯，退回上一层换别的数。
回溯 · 撤销 1：这条分支探完了，撤销选择：把 1 从路径弹出、改回「没用过」（重新亮起）。回到这一层，准备试下一个数。
回溯 · 撤销 3：这条分支探完了，撤销选择：把 3 从路径弹出、改回「没用过」（重新亮起）。回到这一层，准备试下一个数。
回溯 · 撤销 2：这条分支探完了，撤销选择：把 2 从路径弹出、改回「没用过」（重新亮起）。回到这一层，准备试下一个数。
选 3 · 第 1 位：第 1 位：从没用过的数里选 3 放进路径，标记它已用（变灰）。当前 path = [3]，继续往下填。
选 1 · 第 2 位：第 2 位：从没用过的数里选 1 放进路径，标记它已用（变灰）。当前 path = [3, 1]，继续往下填。
选 2 · 第 3 位：第 3 位：从没用过的数里选 2 放进路径，标记它已用（变灰）。当前 path = [3, 1, 2]，继续往下填。
凑齐排列 · [3,1,2]：path 长度到 3 了，凑齐一个完整排列 [3, 1, 2]！记进结果 res（现在有 5 个）。接着回溯，退回上一层换别的数。
回溯 · 撤销 2：这条分支探完了，撤销选择：把 2 从路径弹出、改回「没用过」（重新亮起）。回到这一层，准备试下一个数。
回溯 · 撤销 1：这条分支探完了，撤销选择：把 1 从路径弹出、改回「没用过」（重新亮起）。回到这一层，准备试下一个数。
选 2 · 第 2 位：第 2 位：从没用过的数里选 2 放进路径，标记它已用（变灰）。当前 path = [3, 2]，继续往下填。
选 1 · 第 3 位：第 3 位：从没用过的数里选 1 放进路径，标记它已用（变灰）。当前 path = [3, 2, 1]，继续往下填。
凑齐排列 · [3,2,1]：path 长度到 3 了，凑齐一个完整排列 [3, 2, 1]！记进结果 res（现在有 6 个）。接着回溯，退回上一层换别的数。
回溯 · 撤销 1：这条分支探完了，撤销选择：把 1 从路径弹出、改回「没用过」（重新亮起）。回到这一层，准备试下一个数。
回溯 · 撤销 2：这条分支探完了，撤销选择：把 2 从路径弹出、改回「没用过」（重新亮起）。回到这一层，准备试下一个数。
回溯 · 撤销 3：这条分支探完了，撤销选择：把 3 从路径弹出、改回「没用过」（重新亮起）。回到这一层，准备试下一个数。
全部完成 · 6 个排列：决策树全部走完，6 个排列一个不漏地收齐：[1,2,3]、[1,3,2]、[2,1,3]、[2,3,1]、[3,1,2]、[3,2,1]。回溯的威力就在于：一棵树把所有可能性系统地枚举了一遍，靠「选了再撤」不重不漏。
边界先想清：空数组返回含一个空排列的列表；单元素一种；逻辑对 n=0/1 都自然成立，不用特判。
三个高频追问：含重复的全排列 II、回溯与 DFS 的关系、以及交换法的等价写法。
参考代码
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复杂度
- 时间：O(n·n!)，共 n! 个排列，每个长度 n 拷贝进结果
- 空间：O(n)，递归深度与 path/used 都是 O(n)（不计结果本身）
易错点
面试追问把动画讲成自己的话
追问如果数组有重复数字（全排列 II）怎么办？
追问回溯和 DFS 是一回事吗？
追问能不交换数组、不用 used 吗？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
子集 II
LeetCode 90 · 中等 · 沿着 回溯 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题