Leetcode Hot 100 继续刷，这一题来到回溯题里的经典老演员：全排列。
这类题的气质很统一：
- 要你列出所有可能结果
- 每一步都要做选择
- 选完还得撤回来
翻译成人话就是：
回溯一出场，排列组合先别慌。
这题本身不绕，但非常适合把回溯模板练扎实。 尤其是 Python 里那个老坑：
加入答案时必须用
vals[:]拷贝，不能直接塞vals。
不然回头一改，前面存进去的结果也会跟着串味，像一锅被反复回锅的排列炒饭。
题目链接
题目描述
给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。
你可以按任意顺序返回答案。
解题思路：回溯枚举每一个位置放什么数
全排列的本质，就是把数组里的每个数都安排到排列中的某个位置上。
如果数组长度是 n，那我们就可以把构造答案看成一个“逐位置填数”的过程：
- 第
0位放谁 - 第
1位放谁 - 第
2位放谁 - …
- 直到第
n - 1位也放完
每一层递归都负责确定一个位置上的数字。
需要哪些辅助结构
这题里用两个数组就够了。
1. flag
用于记录某个数是否已经被使用。
flag = [False] * n如果 flag[idx] == True，表示 nums[idx] 已经进了当前排列，
这一轮就不能再选它了。
2. vals
用于保存当前正在构造的排列结果。
vals = [0] * n比如当前已经填到第 2 位，vals 可能长这样：
[2, 1, 0]这里只是举例，最后一位可能还没正式定下来。
代码实现
class Solution(object): def permute(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ ans = [] n = len(nums) if n == 0: return []
flag = [False] * n vals = [0] * n
def dfs(i): if i == n: ans.append(vals[:]) return
for idx, item in enumerate(nums): if flag[idx] == False: vals[i] = item flag[idx] = True dfs(i + 1) flag[idx] = False
dfs(0) return ans回溯过程怎么理解
定义 dfs(i) 表示：
当前要去确定排列中的第
i个位置。
递归终止条件
当 i == n 时，说明长度为 n 的排列已经全部填完。
这时候就得到了一组完整答案：
ans.append(vals[:])然后返回上一层，继续尝试其他选择。
当前层要做什么
在第 i 层，我们要从 nums 里找一个还没被使用过的数，放到 vals[i] 上。
for idx, item in enumerate(nums): if flag[idx] == False: vals[i] = item flag[idx] = True dfs(i + 1) flag[idx] = False这一段就是标准回溯三连：
- 做选择
- 递归进入下一层
- 撤销选择
简写成一句话就是：
选一个，钻下去；回来后，擦干净，再选下一个。
为什么必须写 ans.append(vals[:])
这题里最容易翻车的，不是回溯逻辑， 而是 Python 列表引用这个老六。
如果你写成：
ans.append(vals)表面上看像是把当前排列加入答案， 实际上加入的是 同一个列表对象的引用。
后面递归继续修改 vals 时，
ans 里之前保存的那些结果也会一起被改掉。
最后很可能出现这种场面：
- 你以为收集了很多排列
- 实际上全都指向同一个
vals - 最终答案长得整整齐齐，全员撞脸
所以这里必须切片拷贝：
ans.append(vals[:])可以理解成：
在回溯现场拍一张快照存起来，别把活体直接丢进仓库。
为什么这里不用恢复 vals[i]
你这版代码回溯时只恢复了：
flag[idx] = False却没有写：
vals[i] = 0这其实没问题。
因为下一次循环选别的数时，vals[i] 会被新的值直接覆盖。
只要“这个数是否被用过”的状态被正确恢复，逻辑就不会乱。
真正必须恢复的是使用标记， 因为别的分支还要重新使用这个数。
举个例子
假设：
nums = [1, 2, 3]第一层：确定第 0 位
可以选：
123
假设先选 1，那么当前：
vals = [1, 0, 0]flag 里 1 对应的位置会被标记成已使用。
第二层：确定第 1 位
此时还能选：
23
如果再选 2，就变成：
vals = [1, 2, 0]第三层：确定第 2 位
只剩 3 可选：
vals = [1, 2, 3]这时把它加入答案。
然后递归返回，撤销 3 的使用状态；
再返回上一层，撤销 2 的使用状态；
继续试其他分支。
整个过程就是一棵标准搜索树。
复杂度分析
设数组长度为 n。
时间复杂度
全排列一共有 n! 种结果，
每一种结果在加入答案时都要复制一个长度为 n 的数组。
所以时间复杂度为：
O(n \times n!)空间复杂度
递归深度最多为 n，
辅助数组 flag 和 vals 也都是长度 n。
所以不考虑最终答案存储时，额外空间复杂度为：
O(n)如果把返回结果也算上，
那答案本身就要占 O(n × n!) 的空间。
这不是算法抠门不够，是排列题天生就这么能生。
这题的关键点
1. 回溯模板要熟
- 做选择
- 递归下一层
- 撤销选择
这个节奏是排列、组合、子集这类题的统一鼓点。
2. 用 flag 防止重复使用
每个数字在一个排列里只能出现一次， 所以必须记录它当前是否已经被选走。
3. Python 里结果要拷贝
ans.append(vals[:])这一句不是细节，是考点。 也是很多人 AC 路上的第一块香蕉皮。
小结
这道题就是标准回溯模板题。
思路很直接：
- 每一层决定当前位置放哪个数
- 已经使用过的数字不能再选
- 当所有位置都填满时，收集答案
如果只记一句话，那就是：
全排列就是“逐位填数 + 使用标记 + 回溯撤销”，Python 里别忘了切片拷贝。
模板题别嫌朴素，回溯题海里很多花样，最后都得回到这套骨架上。 把它练熟，后面见到排列、组合、子集，心里就不会先打鼓，只会先开路。🦐