题目描述
给一组不重复的数，返回它们的所有排列。
思路解析
想象你在一层层做决定：每层挑一个还没用过的数放进路径 path；path 凑满 3 个就记下来；然后撤销刚才的选择，回到上一层换一个数继续。
开始：路径 path 一开始是空的，三个数都没用过，结果 res 也是空。
第1层 · 选 1：第一层先选 1：标记 1 已用，放进 path。path = [1]。
第2层 · 选 2：进入第二层，在剩下的 2、3 里选 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。下面用同样的「选择→递归→撤销」走一遍，你会看到流程和以 1 开头时一模一样。
第2层 · 选 1：剩下 1、3，先选 1。path = [2, 1]。
第3层 · 选 3 · 收集：只剩 3，凑满 [2, 1, 3]，记下来。
撤销回 [2]：撤销 3、再撤销 1，回到 path = [2]。第二层换成 3 再试。
第2层 · 改选 3：第二层选 3。path = [2, 3]。
第3层 · 选 1 · 收集：只剩 1，凑满 [2, 3, 1]。以 2 开头的两种也找齐了。
撤销回开头 · 选 3：一路撤销回空，第一层最后选 3。同样的流程会排出 [3,1,2]、[3,2,1]。
全部找齐：6 种排列不重不漏全部找齐。这就是回溯的威力：系统地穷举所有可能。
子集、组合、组合总和、N 皇后……几乎所有「列出所有可能」的题，都是这套回溯三件套的变体。
参考代码（Python）
1def backtrack(path):
2 if len(path) == len(nums): # 选满了
3 res.append(path[:]) # 收集一份副本
4 return
5 for i in range(len(nums)):
6 if used[i]: continue # 跳过用过的
7 used[i] = True # 做选择
8 path.append(nums[i])
9 backtrack(path) # 往下走
10 path.pop() # 撤销选择
11 used[i] = False复杂度分析
- 时间复杂度：O(n × n!) —— n! 种排列，每种花 O(n) 拷贝
- 空间复杂度：O(n) —— 递归深度 + path
套路模板
选择 → 递归 → 撤销，三件套。子集/组合/排列只改「结束条件」和「选择列表」。
1def backtrack(path):
2 if 满足结束条件:
3 res.append(path[:]) # 注意 [:] 拷贝
4 return
5 for 选择 in 选择列表:
6 if 不能选: continue
7 做选择(path) # append + used=True
8 backtrack(path)
9 撤销选择(path) # pop + used=False易错点
- ❌ res.append(path) → ✅ res.append(path[:])（不拷贝，path 之后被改空，结果会全变空）
- ❌ 做了选择忘了撤销 → ✅ append/pop、used 标记/取消 必须成对（否则别的分支用不到这个数）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。