全排列问题如何用回溯法求解？（LeetCode 46）

简化版

全排列是「不重复数组的所有排列顺序」。用回溯：每一层从所有还没用过的元素里挑一个放进路径，直到路径长度等于 n 就收集一个排列，然后撤销、换下一个。关键是用一个 used[] 布尔数组标记哪些元素已经在当前路径里——排列要考虑顺序，所以每一层都要能选到「前面还没选的」元素。时间复杂度 O(n × n!)。

详细版

List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    boolean[] used = new boolean[nums.length];
    backtrack(nums, new ArrayList<>(), used, res);
    return res;
}
void backtrack(int[] nums, List<Integer> path, boolean[] used, List<List<Integer>> res) {
    if (path.size() == nums.length) {          // 结束条件：填满
        res.add(new ArrayList<>(path));        // 收集一个排列（拷贝）
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;                 // 用过的跳过
        used[i] = true; path.add(nums[i]);     // 做选择
        backtrack(nums, path, used, res);      // 递归
        path.remove(path.size() - 1); used[i] = false; // 撤销
    }
}

选择列表 = 所有 used[i]==false 的元素：排列要顺序，所以每层都从头扫，只跳过已用的。
结束条件 = 路径长度等于 n，此时是一个完整排列。
used[] 是排列问题的标志（区别于组合用 start）。
收集解时 new ArrayList<>(path) 拷贝，否则后续修改会污染已存的解。

完整版教学

一、问题与决策树

全排列：给一个不含重复数字的数组（如 [1,2,3]），返回所有可能的排列（[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]，共 3! = 6 个）。

画决策树：根节点空路径；第一层选第 1 个位置放谁（3 种选择）；第二层在剩下的里选第 2 个位置（2 种）；第三层选最后一个（1 种）。叶子共 3×2×1=6 个，每个叶子是一个完整排列。回溯就是遍历这棵树、在每个叶子收集一个解。

二、排列的关键：用 used 数组标记已选

排列和组合最大的不同：排列在意顺序，[1,2] 和 [2,1] 是两个不同的解。所以每一层做选择时，不能只看「后面的元素」，而要看「所有还没被用过的元素」——第一位选了 2，第二位还得能选回 1。

怎么知道哪些用过了？用一个和数组等长的 boolean[] used：某个下标被放进路径就置 true，撤销时置回 false。每层遍历所有下标，used[i] 为 true 的跳过，其余都是当前能选的。

这正是排列问题的标志：用 used[] 数组决定选择列表。而组合/子集问题用 start 下标（只能往后选），因为它们不看顺序。

三、代码与回溯过程

以 [1,2,3] 走一条分支感受「做选择—递归—撤销」：

选 1 → path=[1], used=[T,F,F]
  选 2 → path=[1,2] → 选 3 → path=[1,2,3] ✔收集
       撤销 3 → path=[1,2]，撤销 2 → path=[1]
  选 3 → path=[1,3] → 选 2 → path=[1,3,2] ✔收集 ...
撤销 1 → path=[]，接着从 2 开头、3 开头重复上面过程

每次递归返回，都要把 path 末尾元素弹出、把对应 used[i] 置回 false，保证下一个选择在干净的状态上进行。

四、为什么是 O(n × n!)

一共有 n! 个排列（叶子）。
每生成一个排列，收集时要拷贝长度为 n 的路径，是 O(n)。
加上内部节点的遍历开销，总量级是 O(n × n!)。

这是阶乘级，所以全排列只适合 n 较小（一般 n ≤ 10 上下）的情况。

五、排列 vs 组合：要不要 used、要不要 start

这是回溯里最需要分清的一对：

	排列	组合 / 子集
在意顺序吗	在意（`[1,2]≠[2,1]`）	不在意（`[1,2]=[2,1]`）
选择列表怎么定	`used[]` 标记已用，每层扫全部	`start` 下标，只能往后选
结束条件	路径长度 = n	到达目标（长度/和/末尾）

一句判断：问「顺序算不算不同」——算，就用 used 做排列；不算，就用 start 做组合。

六、把状态、选择与撤销画成决策树

本题递归状态的精确定义是：第 depth 层选择一个尚未使用的元素，used 与 path 一一对应；叶子 path 长度为 n。状态含义越清楚，结束条件、候选范围和去重位置越容易从题意推出。

进入节点：检查当前状态与剩余目标
枚举候选：先判断约束和剪枝条件
做选择：同步修改 path / used / 约束集合
递归下一层
撤销选择：恢复到进入本节点前的状态

带数字推演：[1,2,3] 的树有 3×2×1=6 个叶子，每个答案复制 3 项。画树时只需展开能体现“同层选择”和“纵向递归”区别的两三层，并标出被剪掉的分支，便能解释去重或剪枝为什么不会漏解。

记忆钩子：回溯不是“递归试一试”，而是维护状态不变量；做选择与撤销必须镜像，剪枝必须证明被删分支不可能产生答案。

七、复杂度、剪枝代价与实现边界

关键实现边界是：输入元素互异；若含重复值必须排序并做同层去重；复制答案不能直接保存可变 path 引用。回溯复杂度不能只写一个固定模板，应说明树深、每层分支数、合法叶子数以及复制答案的成本。

维度	自检问题
状态	参数能否唯一描述当前节点
候选	是否遗漏合法选择或重复枚举
剪枝	条件是必要条件还是拍脑袋
撤销	path、标记和计数是否全部恢复
输出	保存的是快照还是共享可变引用

测试应包含无解、唯一解、多解、最小规模、全部候选相同或冲突密集的输入。对可变字符串、棋盘和标记数组，还应在递归返回后断言状态与进入前一致；这类断言比只比较最终答案更容易定位撤销错误。

八、常见误区与追问

误区：排列题也能只用 start 指针。 排列下一位可选任意未使用元素，需要 used 或交换法。
误区：找到叶子时直接保存 path 引用。 后续撤销会修改同一对象，应复制。
误区：时间复杂度只是 O(n!)。 输出每个长度 n 的排列，通常写 O(n·n!)。
追问：为什么 used 要撤销？ 兄弟分支必须重新获得该元素的选择权。
追问：交换法有什么区别？ 把 depth 位置与后续位置交换，可原地表达已选前缀。
追问：空数组有几个排列？ 组合数学上有一个空排列，具体返回语义按题目约定。

九、加强记忆

全排列回溯：每层从所有 used[i]==false（没用过） 的元素里选，路径长度到 n 就收集（拷贝一份）。used[] 数组是排列的标志——因为排列在意顺序，每层要能选回前面没用的元素；这与组合/子集用 start（只往后选、不看顺序）正好相对。做选择置 used=true、撤销置回 false，成对对称。复杂度 O(n × n!)，阶乘级，只适合小 n。

简化版

详细版