Hot 100 --- 全排列

本文概览：本文以LeetCode题目"全排列"为例，讲解回溯法的核心思路——已选择/未选择的划分，visited数组维护顺序，回溯就是撤销选择换下一个

一、题目

全排列题目

二、题目分析

题目要求：给定一个没有重复数字的数组，返回所有可能的全排列

全排列其实是初高中常遇到的数学题——n 个元素能排成多少个序列？答案是 n!。过程是这样的：

第1次选择：从 n 个元素里选 1 个     → n 种
第2次选择：从剩下的 n-1 个里选 1 个 → n-1 种
第3次选择：从剩下的 n-2 个里选 1 个 → n-2 种
...
第n次选择：只剩 1 个，没得选         → 1 种

总排列数 = n × (n-1 × (n-2 × ... × 1)) = n!

这题的难点不是思路，而是怎么不重不漏地遍历完所有排列。如果随便选，必然会有重复。所以必须按某种顺序系统地遍历，这就需要回溯法

思路概览

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        // 结果列表
        List<List<Integer>> res = new ArrayList<>();
        if (nums.length == 0) {
            return res;
        }
        // 访问数组
        boolean[] visited = new boolean[nums.length];
        // 递归函数
        backtrack(res, visited, nums, new ArrayList<>());
        return res;
    }

    private void backtrack(List<List<Integer>> res, boolean[] visited, int[] nums, ArrayList<Integer> path) {
        // 递归出口
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            // 剪枝
            if (visited[i]) {
                continue;
            }
            // 标记访问过
            visited[i] = true;
            // 添加到当前路径
            path.add(nums[i]);
            // 递归调用
            backtrack(res, visited, nums, path);
            // 回溯
            visited[i] = false;
            // 从当前路径中移除
            path.removeLast();
        }
    }
}

思路简要说明

已选择 / 未选择：用 path 记录已选的元素，用 visited 数组记录每个元素有没有被选过（false = 没选过）。每轮从 i=0 扫到末尾，跳过选过的，选没选过的
回溯 = 撤销选择换下一个：递归回来后，撤销当前选择（visited 设回 false，path 移除最后一个），for 循环 i++ 自动选下一个元素。这就实现了"选完一个换下一个试试"

三、思路详解

第一步：已选择 / 未选择的划分

回忆前面做过的题——无论 DFS 还是 BFS，我们都需要知道"已经处理了什么，还没处理什么"。全排列也一样，可以把数组分成两部分：

已选择：已经加入排列的元素，用 path 列表记录
未选择：还没加入排列的元素，用 visited 数组标记（false 表示未选择）

以 nums = [1, 2, 3] 为例：

初始状态：
  已选择 path = []
  未选择 visited = [false, false, false]  → 1, 2, 3 都可选

选了 1 之后：
  已选择 path = [1]
  未选择 visited = [true, false, false]   → 2, 3 可选

再选了 2 之后：
  已选择 path = [1, 2]
  未选择 visited = [true, true, false]    → 只有 3 可选

第二步：怎么保证不重不漏？

这是这题的核心问题。如果随便选，比如先选 2 再选 1，和先选 1 再选 2，可能会产生重复的遍历路径

解决办法很简单：每一轮都从 i=0 开始扫描，遇到选过的就跳过，选第一个没选过的。因为 for 循环永远从 0 开始，选过的元素会被 if (visited[i]) continue 跳过，没选过的元素会按数组下标顺序依次被选中

nums = [1, 2, 3]，假设 1 已经选过了：

i=0: visited[0]=true  → 跳过
i=1: visited[1]=false → 选 2
i=2: visited[2]=false → 选 3

没选过的 2、3 会按数组顺序被选到，不会乱

每次都是按固定顺序选，不可能产生重复

第三步：回溯是什么？

回溯就是撤销当前选择，换下一个试试

用 nums = [1, 2, 3] 举例，手动模拟一遍全过程：

第一轮：全选第一个
  选 1 → path = [1]
    选 2 → path = [1, 2]
      选 3 → path = [1, 2, 3]  ✓ 第1个排列
      回溯：撤销 3，path = [1, 2]
    没有其他可选了
    回溯：撤销 2，path = [1]
    选 3 → path = [1, 3]
      选 2 → path = [1, 3, 2]  ✓ 第2个排列
      回溯：撤销 2，path = [1, 3]
    没有其他可选了
    回溯：撤销 3，path = [1]
  没有其他可选了
  回溯：撤销 1，path = []

第二轮：从倒数第二个开始换
  选 2 → path = [2]
    选 1 → path = [2, 1]
      选 3 → path = [2, 1, 3]  ✓ 第3个排列
      ...
    选 3 → path = [2, 3]
      选 1 → path = [2, 3, 1]  ✓ 第4个排列
      ...
  回溯：撤销 2，path = []

第三轮：换到第一个位置的第三个元素
  选 3 → path = [3]
    选 1 → path = [3, 1]
      选 2 → path = [3, 1, 2]  ✓ 第5个排列
      ...
    选 2 → path = [3, 2]
      选 1 → path = [3, 2, 1]  ✓ 第6个排列
      ...
  回溯：撤销 3，path = []

6 个排列，正好是 3! = 6。观察整个过程：

第一轮全选第一个，得到 [1,2,3]
然后从倒数第二个开始回溯，换一个选择，得到 [1,3,2]
再往上一层回溯，从倒数第三个开始换，选第二个元素 2，然后重复第一轮第二轮的操作
再从倒数第三个换到第三个元素 3，重复操作

这就是回溯的本质——从最深处开始撤销，换一个选择，换完后继续往下走；这一层换完了就退到上一层再换

第四步：代码怎么对应这个过程？

for (int i = 0; i < nums.length; i++) {
    if (visited[i]) continue;       // ① 跳过已选的
    visited[i] = true;              // ② 标记选择
    path.add(nums[i]);              // ③ 加入路径
    backtrack(...);                 // ④ 往下递归
    visited[i] = false;             // ⑤ 回溯：撤销标记
    path.removeLast();              // ⑥ 回溯：移出路径
}

①②③：选择当前元素
④：带着这个选择往下走，处理剩余元素
⑤⑥：递归回来后撤销选择，for 循环 i++ 自动选下一个

for 循环就是"遍历所有可选元素"，回溯就是"选完了换下一个"。不需要手动控制"从倒数第几个开始换"——for 循环 + 递归自然就实现了这个逻辑

第五步：递归出口

if (path.size() == nums.length) {
    res.add(new ArrayList<>(path));
    return;
}

当 path 的长度等于 nums 的长度时，说明所有元素都选完了，这是一个完整的排列。注意要用 new ArrayList<>(path) 创建副本——如果直接 add(path)，后续回溯修改 path 会影响已经存入的结果

第六步：完整执行过程图解

以 nums = [1, 2, 3] 为例，用缩进表示递归深度：

path = []  visited = [F, F, F]

  i=0: 选 1 → path = [1]  visited = [T, F, F]
    i=0: 跳过（已访问）
    i=1: 选 2 → path = [1,2]  visited = [T, T, F]
      i=0: 跳过
      i=1: 跳过
      i=2: 选 3 → path = [1,2,3]  ✓ 加入结果
      回溯：path = [1,2]  visited = [T, T, F]
    回溯：path = [1]  visited = [T, F, F]
    i=2: 选 3 → path = [1,3]  visited = [T, F, T]
      i=0: 跳过
      i=1: 选 2 → path = [1,3,2]  ✓ 加入结果
      回溯：path = [1,3]
    回溯：path = [1]
  回溯：path = []  visited = [F, F, F]

  i=1: 选 2 → path = [2]  visited = [F, T, F]
    i=0: 选 1 → path = [2,1]  visited = [T, T, F]
      i=2: 选 3 → path = [2,1,3]  ✓ 加入结果
    回溯...
    i=2: 选 3 → path = [2,3]  visited = [F, T, T]
      i=0: 选 1 → path = [2,3,1]  ✓ 加入结果
    回溯...
  回溯：path = []

  i=2: 选 3 → path = [3]  visited = [F, F, T]
    i=0: 选 1 → path = [3,1]  visited = [T, F, T]
      i=1: 选 2 → path = [3,1,2]  ✓ 加入结果
    回溯...
    i=1: 选 2 → path = [3,2]  visited = [F, T, T]
      i=0: 选 1 → path = [3,2,1]  ✓ 加入结果
    回溯...
  回溯：path = []

最终结果：[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]，共 6 个

复杂度分析

时间复杂度：O(n × n!)，共 n! 个排列，每个排列需要 O(n) 时间复制到结果
空间复杂度：O(n)，递归深度最大为 n，visited 数组和 path 都是 O(n)