全排列
交换式回溯每次固定一个位置：把剩余值交换到 start，递归处理后缀，再重复同一交换，恢复调用者收到的数组。n 个不同值产生 n! 个排列。
每次调用像借用数组，可以重排后缀，但返回时必须原样归还。这样调用者才能尝试下一选择，不必重建状态。允许修改工作数组、需要全部顺序时适合交换法；不便修改共享数组时，可用 path + remaining，但会分配更多临时数组。
递归选择如何工作
nums = [1, 2, 3]，先调用 backtrack(0)。位置 0 依次尝试：
- 自交换保留 1，递归处理
[2, 3]。 - 把 2 换入，递归处理
[1, 3]。 - 把 3 换入，递归处理
[2, 1]。
第一个分支的 backtrack(1) 先保留 2，下一层只剩 3，输出 [1, 2, 3]。返回并恢复后，再把 3 换到位置 1，输出 [1, 3, 2]。
根尝试第二个选择前，内部交换已经逐层撤销，根的自交换也已撤销，数组恢复 [1, 2, 3]。动画在此比较保存的调用者快照与返回数组，确认两者相等，再交换位置 0、1。
画布为元素保留稳定身份，重复值也能分清来自哪个位置；代码仍使用普通数值数组。
为什么有 n! 个叶子
第 0 层 n 个选择，第 1 层 n−1 个，最后一层一个：
n * (n - 1) * ... * 1 = n!
三个元素对应 3 * 2 * 1 = 6。每个因子是一层的位置选择，每条完成路径到达一个基础状态。
基础状态必须把当前数组复制到 result。原 nums 还会继续交换；若只追加同一个引用，所有结果会随它改变，最后都变成恢复后的同一顺序。
回溯不变量
对 backtrack(start)：每次循环开始前，nums 的顺序都应与本调用刚收到时完全一致。
正向交换构造子状态。子调用可进行很多深层交换，但它返回前先恢复自己的入场状态。当前层再做逆交换，就恢复本层入场状态。
所以一行交换不是独自撤销整棵子树，而是建立在每个后代都履行恢复约定的基础上。去掉逆交换后，只要有三个及以上不同值，就会有排列重复、有排列缺失。[1, 2] 只是碰巧没出错：首个子树只做了自交换，第二个根选择仍从 [1, 2] 开始。只递归而不恢复，不是完整的回溯。
不恢复会怎样
No restore 只去掉第二次交换。[1, 2, 3] 的首个根子树返回 [1, 3, 2]，没有恢复 [1, 2, 3]，下一兄弟分支从错误状态开始。
仍访问六个叶子，但只有四种值序列：[1, 2, 3]、[1, 3, 2]、[3, 1, 2]、[3, 2, 1]。前两项各重复一次，[2, 1, 3] 和 [2, 3, 1] 完全缺失。基础状态访问六次不代表得到六种排列。
逐步演示
默认 [1, 2, 3] 的完整恢复流程：
- 根选 1，自交换；第 1 层保留 2，第 2 层保留 3，复制
[1, 2, 3]。 - 撤销两层自交换，第 1 层改选 3，复制
[1, 3, 2]；逐层撤销后，根数组恢复[1, 2, 3]。 - 根选 2，交换位置 0、1，得到
[2, 1, 3]。第 1 层依次选 1、3，输出[2, 1, 3]、[2, 3, 1]。 - 子树返回并恢复
[1, 2, 3]；根选 3，交换位置 0、2，得到[3, 2, 1]。 - 第 1 层先保留 2，再交换 1、2 两位置，输出
[3, 2, 1]、[3, 1, 2]。 - 最后所有逆交换恢复
[1, 2, 3]，返回六个独立副本。
| 根选择 | 内层选择 | 输出 |
|---|---|---|
| 位置 0 放 1 | 2，再 3 | [1, 2, 3]、[1, 3, 2] |
| 位置 0 放 2 | 1，再 3 | [2, 1, 3]、[2, 3, 1] |
| 位置 0 放 3 | 2，再 1 | [3, 2, 1]、[3, 1, 2] |
结果栏按首位置的稳定元素身份分组，每组 (n - 1)! 项；调用栈显示当前处理哪个因子。i === start 的自交换是真实步骤，虽然值不动，却让各层使用同一条循环规则。
重复值与唯一排列
算法区分位置。[1, 1, 2] 的两个 1 身份不同，仍有 3! = 6 个位置叶子，但值序列只有 [1, 1, 2]、[1, 2, 1]、[2, 1, 1]，每项两次。
重复值预设保留全部六次追加，并把重复结果连接到首次出现，不会暗中去重。若要求唯一排列，应在同一递归深度跳过相同值，常用该层局部 used 集合。先生成全部再对结果去重仍支付了重复的阶乘工作。
时间与空间复杂度
| 项目 | 界 | 原因 |
|---|---|---|
| 叶子数 | n! | 每层有 n−start 个位置选择 |
| 时间 | Θ(n × n!) | 每叶复制 n 个值 |
| 递归辅助空间 | O(n) | 最多 n+1 个活动栈帧 |
| 返回结果空间 | Θ(n × n!) | n! 个长度 n 的数组 |
原地交换缩小搜索状态，不能消除输出成本。画布最多四个元素，四元素的 24 个叶子按教学节奏也需约 2 分 35 秒。n = 12 时已有 12! = 479,001,600 个叶子，每个还要复制十二个值。
小规模全排列可用于暴力旅行商路线、字母排列、短排程。实际使用前应确认 n 足够小，或约束能剪去大部分分支，否则完整枚举通常不可行。
边界情况
- 单元素只有一个排列，经历自交换、基础状态复制和恢复。
- 空数组通常定义有一个空排列。本课仅接受一到四元素，实际代码可支持数学上的空情况。
- 负数和重复值都可作为内容，遍历顺序由位置而非数值决定。
- 反转循环顺序仍可生成不同值输入的同一结果集合，但输出顺序改变。
- Python 用
nums.copy()，JavaScript 用[...nums]保存副本。
常见错误
- 忘记逆交换。 下一兄弟继承被修改数组；只要有三个及以上不同值，就会有排列重复、有排列缺失。
- 直接追加可变数组。 多个结果引用同一对象，后续交换改写历史答案。
- 递归推进 i。 应调用
backtrack(start + 1)，固定前缀长度与循环候选索引不同。 - 用全局 used 做去重。 一分支用过的值在兄弟分支仍可用，去重范围应是当前深度。
- 把每个叶子都称为唯一值排列。 n! 统计位置选择；只有输入值不同才等于唯一值序列数。
无论采用哪种状态表示，都要选择、递归，并在返回时恢复调用者原有状态。