LeetCode 46：全排列（Permutations）题解

Permutations 是 LeetCode Hot 100 里面一道非常经典的回溯题。

这道题在回溯专题里几乎可以算是“必做题”。因为它的结构非常标准，逻辑也很清晰，非常适合用来理解回溯算法里最核心的几个概念：

当前路径是什么
当前有哪些选择
如何标记某个元素已经使用过
为什么递归结束后还要恢复现场

你给出的这份 Java 代码，就是这道题最经典、最标准的一种写法。它通过一个 used 数组来记录哪些数字已经被选过，然后一层层构造排列，直到路径长度等于数组长度时，就得到一组完整答案。

本文就结合这段代码，系统地讲一下这道题的解法思路。

题目介绍

给定一个 不含重复数字 的数组 nums，返回它的所有可能全排列。

所谓全排列，就是把数组中的所有元素按不同顺序全部列出来。

例如：

nums = [1,2,3]

它的全排列共有 6 种：

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

因为数组中一共有 3 个元素，所以排列总数是：

3! = 6

题目要求我们把所有排列都返回出来。

示例

示例 1

输入：nums = [1,2,3]
输出：
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

示例 2

输入：nums = [0,1]
输出：[[0,1],[1,0]]

两个元素的排列只有两种，互换顺序即可。

示例 3

输入：nums = [1]
输出：[[1]]

只有一个元素时，全排列当然就只有它自己。

为什么这道题适合用回溯？

因为全排列本质上就是一个“逐位做选择”的过程。

假设数组是：

[1,2,3]

那么排列的第一个位置可以选：

如果第一个位置选了 1，那么第二个位置就只能从剩下的：

里面选。

如果第二个位置选了 2，那第三个位置就只能选 3。

也就是说，这道题的求解过程天然就是一棵搜索树：

第一层决定第一个位置放什么
第二层决定第二个位置放什么
第三层决定第三个位置放什么
当路径长度等于数组长度时，就得到一组完整排列

这正是回溯算法最擅长处理的场景。

最直接的思路是什么？

如果从最朴素的角度去想，全排列就是：

把每个数字都尝试放到当前排列的下一个位置
但已经用过的数字不能再用
一直递归下去，直到排列长度等于数组长度

所以这道题的关键点主要有两个：

如何记录当前已经选了哪些数字
如何在递归结束后恢复现场，继续尝试别的分支

这也正是回溯的典型套路。

核心思路

你的代码采用的是最经典的一种做法：

用 path 记录当前已经构造出来的排列
用 used[i] 表示下标 i 对应的数字是否已经被使用过
每一层遍历所有数字
如果某个数字还没被用过，就把它加入路径
然后递归处理下一层
递归回来后，再把这个数字从路径中删除，并把 used[i] 恢复成 false

这就是一整套标准的“回溯三部曲”：

做选择
递归
撤销选择

Java 代码

下面是你给出的代码，我这里保留原始逻辑，并加上注释：

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        boolean[] used = new boolean[nums.length];

        backtrack(nums, result, path, used);
        return result;
    }

    private void backtrack(int[] nums, List<List<Integer>> result, List<Integer> path, boolean[] used) {
        // 如果当前路径长度已经和数组长度相同，说明得到一个完整排列
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            // 如果当前数字已经被使用过，就跳过
            if (used[i]) continue;

            // 做选择
            path.add(nums[i]);
            used[i] = true;

            // 递归进入下一层
            backtrack(nums, result, path, used);

            // 撤销选择
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

代码拆解

这段代码是回溯题里非常标准的模板。如果你能把这份代码真正理解透，那么后面很多排列、组合、子集类问题都会顺很多。

1. `permute` 函数在做什么？

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used = new boolean[nums.length];

    backtrack(nums, result, path, used);
    return result;
}

主函数主要做了三件事：

创建结果集 result
创建当前路径 path
创建标记数组 used

然后从空路径开始回溯搜索。

`result`

用来存放所有完整排列。

`path`

表示当前递归过程中，已经选出来的排列前缀。

`used`

表示每个位置上的数字是否已经被使用过。

这三个变量基本就是这道题最重要的状态。

2. `backtrack` 函数的含义是什么？

private void backtrack(int[] nums, List<List<Integer>> result, List<Integer> path, boolean[] used)

这个函数表示的是：

在当前路径 path 的基础上，从还没使用过的数字中继续挑选，直到生成一个完整排列。

这里没有显式写“当前处理到第几层”，因为这一信息已经隐含在：

path.size()

里了。

也就是说：

当 path.size() == 0，说明正在选第 1 个位置
当 path.size() == 1，说明正在选第 2 个位置
当 path.size() == nums.length，说明整个排列已经构造完成

这是这道题一个很常见的小技巧。

3. 为什么 `path.size() == nums.length` 时就可以加入答案？

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

因为全排列要求的是：

每个数字都恰好出现一次。

所以当当前路径长度已经等于数组长度时，就说明：

所有数字都已经选完了
当前路径就是一个完整排列

这时候就应该把它加入结果集。

注意这里一定要写成：

new ArrayList<>(path)

而不能直接写：

result.add(path)

因为 path 是一个会不断修改的对象。如果直接把它本身放进去，后续回溯修改路径时，结果集中的内容也会被一起改掉。

所以必须拷贝一份当前路径。

4. 为什么要遍历所有数字？

for (int i = 0; i < nums.length; i++) {

因为当前层的任务是：

从所有还没被使用过的数字里，选一个放到当前位置。

全排列和组合题不一样。组合题通常会有一个 start 参数，因为组合不关心顺序；但排列关心顺序，所以每一层都必须重新遍历整个数组，看看哪些数字还可用。

这也是全排列和子集/组合类题目最本质的区别之一。

5. 为什么 `used[i]` 为 `true` 时要跳过？

if (used[i]) continue;

因为题目要求每个数字在一个排列里只能出现一次。

如果某个数字已经出现在当前路径中，那它就不能再被选了。 used[i] 的作用，就是帮助我们快速判断这个数字有没有被用过。

例如：

nums = [1,2,3]

如果当前路径已经是：

[1,3]

那么此时：

used[0] = true
used[2] = true

这说明 1 和 3 都已经被选过了，当前层就只能选择 2。

6. 为什么这是标准的回溯三部曲？

path.add(nums[i]);
used[i] = true;

backtrack(nums, result, path, used);

path.remove(path.size() - 1);
used[i] = false;

这四行代码就是整道题最核心的部分。

第一步：做选择

path.add(nums[i]);
used[i] = true;

表示把当前数字加入路径，并标记为已使用。

第二步：递归进入下一层

backtrack(nums, result, path, used);

去为下一个位置继续选择数字。

第三步：撤销选择

path.remove(path.size() - 1);
used[i] = false;

把当前数字从路径中删除，并恢复成“未使用”状态。

这样后面循环到别的数字时，搜索树的其他分支才能正常进行。

这一步非常重要。如果不撤销选择，那么一条分支对状态的修改就会污染其他分支，结果一定会错。

手动模拟一遍

我们用最经典的例子来走一遍：

nums = [1,2,3]

初始状态

path = []
used = [false, false, false]

开始第一层搜索。

第一层：选择 `1`

path = [1]
used = [true, false, false]

进入下一层。

第二层：在剩下数字里选

此时可以选：

选择 `2`

path = [1,2]
used = [true, true, false]

进入下一层。

第三层：只能选 `3`

path = [1,2,3]
used = [true, true, true]

此时路径长度等于数组长度，得到一个完整排列：

[1,2,3]

加入结果集。

然后开始回退：

删除 3
恢复 used[2] = false

回到第二层。

第二层：改选 `3`

path = [1,3]
used = [true, false, true]

下一层只能选 2，于是得到：

[1,3,2]

加入结果集。

第一层：回退后改选 `2`

同样会生成：

[2,1,3]
[2,3,1]

第一层：再改选 `3`

会生成：

[3,1,2]
[3,2,1]

最终总共得到 6 种排列。

为什么不会漏掉答案？

因为每一层都完整地尝试了所有还没被使用过的数字。

对于长度为 n 的数组：

第 1 层有 n 种选择
第 2 层有 n - 1 种选择
第 3 层有 n - 2 种选择
…
最后一层有 1 种选择

这正好覆盖了所有可能排列。

所以不会漏解。

为什么不会出现重复答案？

因为题目已经说明：

数组中没有重复数字。

再加上我们用 used 保证每个数字在一个排列中只使用一次，所以每条路径都唯一对应一个排列。

因此不会出现重复结果。

如果题目中数组里允许重复数字，那就不是这道题了，而是“全排列 II”，那时就需要额外处理去重逻辑。

复杂度分析

时间复杂度

长度为 n 的数组一共有：

n!

种排列。

而每生成一个排列，都需要把当前路径拷贝进结果集，这一步是 O(n)。

所以总时间复杂度通常写作：

O(n × n!)

空间复杂度

额外空间主要来自：

递归调用栈
当前路径 path
标记数组 used

递归深度最多为 n，所以辅助空间复杂度为：

O(n)

如果把结果集本身也算进去，那么整体空间会更大，因为需要存下所有排列。

这道题真正想考什么？

这道题表面上是在求全排列，但本质上非常适合训练回溯的基本功。

第一，是否能正确理解“路径”和“选择”

你必须非常清楚：

当前路径记录的是什么
当前层有哪些候选数字
哪些数字已经不能再选

如果这些状态没想明白，代码很容易写乱。

第二，是否能熟练写出“做选择、递归、撤销选择”的结构

这几乎是所有回溯题的共同骨架。

全排列这道题特别适合拿来练这个模板，因为它逻辑纯粹，没有太多额外剪枝干扰。

第三，是否能理解排列和组合的区别

组合类题目通常要传 start，因为顺序不重要；而排列类题目没有 start，因为每一层都要从全部未使用数字里重新选。

这个区别非常重要。

和“子集”“组合总和”有什么区别？

很多人在学回溯时，会把这些题混在一起。其实它们的结构虽然相似，但目标不同。

子集

每个元素可以“选”或“不选”，关注的是所有可能集合。

组合总和

要让路径中的数字和等于目标值，通常还会带剪枝和 start 控制。

全排列

要求把所有数字排出不同顺序，因此每层都要遍历整个数组，并用 used 控制是否已被使用。

也就是说：

全排列的关键不是 start，而是 used。

这是这道题最核心的特征。

总结

这道题的核心思想可以概括成一句话：

通过回溯逐位构造排列，每一层从所有未使用过的数字中选择一个加入当前路径，直到路径长度等于数组长度。

具体步骤就是：

用 path 记录当前排列路径
用 used 数组记录哪些数字已经被使用
当路径长度等于数组长度时，把当前路径加入结果集
否则遍历所有数字，挑选未使用的数字加入路径
递归进入下一层
回来后撤销选择，继续尝试别的分支

这是一道非常经典、也非常值得反复练习的回溯题。因为它几乎把回溯最核心的那套框架完整展示了出来：

路径记录
状态标记
递归搜索
撤销选择

把这道题真正吃透之后，再去看：

全排列 II
N 皇后
组合
子集

这些回溯题时，你会更容易看出它们之间共通的骨架。

因为“全排列”本身就是回溯入门题里最经典的一道模板题。