LeetCode LCR 083. 全排列

2026-03-28 HGNULB 约 9 分钟

文章信息 5 个分类 3 个标签

分类

LeetCode 中等 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 083. 全排列

题意分析

给一个元素互不相同的整数数组 nums，返回它所有可能的排列。排列与组合的分水岭在于顺序有意义：[1,2,3] 和 [3,2,1] 是两个不同的答案，都要输出。答案之间不要求任何顺序。

「元素互不相同」这条约束值千金——它意味着不同的下标选法一定对应不同的值序列，完全不需要去重。这直接把本题从「全排列 II」的难度降到了模板级：只要保证每个下标恰好被用一次，产出的方案自然两两不同。

数组长度上界只有 6，$6! = 720$ 种排列，规模小到可以毫无顾虑地暴力枚举。这个上界本身就是出题人给的信号：本题考的不是优化，而是能否把「枚举所有排列」这件事组织成一段结构清晰、无重无漏的递归。元素取值范围 [-10, 10] 含负数，所以任何依赖「值非负」的技巧（比如拿值当数组下标做标记）都不能用。

边界：长度为 1 时答案是包含单个排列的列表 [[x]]，而不是空列表；答案总数恰为 $n!$，可以拿来自查有没有漏解或重解。

解法：回溯搜索

核心思路

暴力的想法是：第 1 个位置有 $n$ 种选法，第 2 个位置有 $n-1$ 种，依此类推。问题在于「剩下哪些数还没用」这个信息必须被显式维护——如果每次都去扫描当前路径判断某个数用没用过，单次判断就要 $O(n)$，而且路径里存的是值，遇到重复值会失效。

关键观察是：「还剩哪些数可用」完全由一个长度为 $n$ 的布尔数组刻画，used[i] 表示下标 i 的元素是否已在当前路径中。用下标而非值来标记，既是 $O(1)$ 判断，也为后续的「全排列 II」留下了扩展空间。

于是把问题按「位置」逐层填充：递归的第 u 层负责决定排列的第 u 个位置放谁。要维持的不变量是：path 的前 u 个位置已填好且两两不同，used 中恰好有 u 个 true，且它们与 path 前 u 位一一对应。每一层横向枚举所有 used[i] == false 的下标，把 nums[i] 放到第 u 位，标记 used[i] = true 后进入第 u+1 层；回溯时撤销标记，让该下标重新可用。

递归基是 u == n：此时 n 个位置全部填满，path 就是一个完整排列，拷贝入结果。由于每层的横向枚举互不相同（不同的 i），而不同的 i 对应不同的值（元素互不相同），所以 $n!$ 条路径两两不同、不重不漏。

解题步骤

准备三样东西：结果列表 res、当前路径 path、使用标记 used。used 的长度等于数组长度，初值全 false，语义是「下标 i 的元素尚未被放入路径」。用下标标记而不是用值标记，是这个模板能平滑升级到含重复元素版本的原因。

递归基判在开头：u == n 说明所有位置已填满，把 path 深拷贝一份存入 res 后返回。深拷贝不可省，path 是全程复用的同一个容器。

横向枚举所有下标：for (int i = 0; i < n; ++i)。注意起点是 0 而不是 u——排列允许「回头」选用更小下标的元素，这正是排列与组合在代码上最直观的区别。组合题里的下标单调是为了消除顺序，而本题恰恰要保留顺序。

跳过已用元素：if (!used[i]) 才进入。这是「每个元素恰好用一次」的唯一保障。

选择、递归、撤销：先 path.add(nums[i]) 与 used[i] = true，再 dfs(u + 1, ...)，返回后按相反顺序撤销 used[i] = false 与 path.remove(path.size() - 1)。两个状态必须同时撤销，只撤一个会让 used 与 path 失去对应关系，不变量被破坏。

Go 版的一个细节：path 预分配为长度 n 的切片并用 path[u] = nums[i] 直接按位赋值，因此不需要撤销 path——下一次循环会把同一个位置覆写掉，而第 u 位之后的旧值永远不会被读到（只有 u == n 时才拷贝，那时前 n 位全部是本轮写入的）。这是按位赋值相对于 append 的一个小便利。

以 nums = [1, 2, 3] 走一遍，记 path | used 的状态。

进入 dfs(u=0)，used = [F,F,F]，横向枚举 i = 0,1,2。

i = 0：填入 1，path = [1]，used = [T,F,F]，进入 dfs(1)。该层 i = 0 已用跳过；i = 1 填入 2，path = [1,2]，used = [T,T,F]，进入 dfs(2)；该层只有 i = 2 可用，填入 3，path = [1,2,3]，进入 dfs(3)，u == n 命中，记下第一个排列 [1,2,3]。逐层回溯：撤销 3，回到 dfs(2) 循环结束；撤销 2 得 path = [1]、used = [T,F,F]。

回到 dfs(1) 继续 i = 2：填入 3，path = [1,3]，used = [T,F,T]，进入 dfs(2)，唯一可用的 i = 1 填入 2，得第二个排列 [1,3,2]。回溯到 dfs(0)，撤销 1，used 复原为 [F,F,F]。

i = 1：以 2 开头，同样的两层展开依次产出 [2,1,3] 和 [2,3,1]。i = 2：以 3 开头，产出 [3,1,2] 和 [3,2,1]。

最终 res 含 6 个排列，恰为 $3! = 6$，与理论值吻合。若漏掉 used[i] = false 的撤销，[1,2,3] 产出后 used 永远保持全 T，dfs(0) 的 i = 1、i = 2 分支一个都进不去，答案只剩 1 条；若把循环起点写成 u，就退化成了「只输出下标递增的一种选法」，答案只剩 [1,2,3] 这唯一一条。

代码实现

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        int n = nums.length;
        // used[i] 表示下标 i 的元素是否已在当前路径中。
        boolean[] used = new boolean[n];
        dfs(0, n, nums, used, path, res);
        return res;
    }

    // u：当前要填充的位置。
    private void dfs(
        int u, int n, int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
        if (u == n) {
            // path 全程复用，必须深拷贝。
            res.add(new ArrayList<>(path));
            return;
        }
        // 从 0 开始枚举：排列允许回头选更小的下标。
        for (int i = 0; i < n; ++i) {
            if (!used[i]) {
                path.add(nums[i]);
                used[i] = true;
                dfs(u + 1, n, nums, used, path, res);
                // path 与 used 必须一起撤销。
                used[i] = false;
                path.remove(path.size() - 1);
            }
        }
    }
}

func permute(nums []int) [][]int {
    n := len(nums)
    res := make([][]int, 0)
    // path 预分配定长，按位赋值，不需要显式撤销。
    path := make([]int, n)
    // used[i] 表示下标 i 的元素是否已在当前路径中。
    used := make([]bool, n)
    dfs(0, n, nums, used, path, &res)
    return res
}

// u：当前要填充的位置。
func dfs(u, n int, nums []int, used []bool, path []int, res *[][]int) {
    if u == n {
        t := make([]int, n)
        copy(t, path)
        *res = append(*res, t)
        return
    }
    // 从 0 开始枚举：排列允许回头选更小的下标。
    for i := 0; i < n; i++ {
        if !used[i] {
            path[u] = nums[i]
            used[i] = true
            dfs(u+1, n, nums, used, path, res)
            used[i] = false
        }
    }
}

复杂度分析

时间复杂度：$O(n \times n!)$，一共产出 $n!$ 个排列，每个排列在递归基处需要 $O(n)$ 时间拷贝。搜索树的内部节点数是 $O(n!)$ 量级，每个节点做 $O(n)$ 次横向枚举，总量同阶。输出全部排列的题目，这个下界无法绕过。

空间复杂度：$O(n)$，递归栈深度恰为 n，path 长度为 n，used 长度为 n，三者都与输入规模同阶。返回值 res 是题目要求的输出，按惯例不计入额外空间。

关键点总结

排列与组合在代码上的唯一区别是循环起点：组合从 u 开始（下标单调，消除顺序），排列从 0 开始（允许回头，保留顺序）。用这一句就能向面试官说明白两族题目的关系。

「哪些元素还可用」要用下标标记而不是值标记，used 数组是 $O(1)$ 判断，且天然支持含重复值的输入；用 path.contains(nums[i]) 既是 $O(n)$ 又会在重复值上出错。

回溯撤销必须成套：本题同时改了 path 和 used 两处状态，就要撤销两处。一个通用检查法是「递归调用前改了几行，返回后就要还原几行」。

元素互不相同这条前提直接豁免了去重逻辑，做题时要主动去读这一条；一旦题目允许重复元素，本模板必须补上排序与同层跳过，那就是「全排列 II」。

答案数量 $n!$ 可以当作自查手段：写完随手用 n = 3 验证输出是不是 6 条，重解和漏解都能一眼发现。这个「用规模自查」的习惯在面试白板上尤其有用。

易错点总结

循环起点写成 i = u：nums = [1,2,3] 只会输出 [[1,2,3]] 一条，因为下标被强制递增，退化成了组合。

忘记 used[i] = false：nums = [1,2,3] 产出 [1,2,3] 后所有标记停留在 true，后续分支全部进不去，答案只剩 1 条而不是 6 条。

只撤销 used 而忘记 path.remove：nums = [1,2] 时 path 会不断累积，第二个排列被记成 [1,2,2,1] 之类的超长数组。

把 path 的引用直接放进 res：nums = [1,2,3] 最终得到 6 个内容相同的空列表，因为搜索结束时共享的 path 已被清空。

Go 里写 *res = append(*res, path)：所有结果共享同一个底层数组，最后 6 条全变成最后一个排列 [3,2,1]，必须 copy 到新切片。

用 path.contains(nums[i]) 代替 used 数组判重：nums = [1,2,3] 结果虽对，但每次判断退化为 $O(n)$；更要命的是这个写法一旦用到含重复元素的变体上，nums = [1,1,2] 会把第二个 1 误判为已用，直接漏解。

递归基写成 path.size() == n 却又忘了在 Go 里同步：Go 版 path 是定长切片，len(path) 恒为 n，这个条件在第一次调用就成立，会立刻输出一个全 0 的假答案。

在递归基处直接 return 之前忘了 return：命中后继续往下走，u 超过 n，Go 版 path[u] = nums[i] 会数组越界 panic。

误以为需要排序或去重：nums = [1,2,3] 排序不影响正确性，但会让人误以为本题和「全排列 II」是同一套逻辑；面试中被问「为什么不去重」而答不上「元素互不相同」，说明没读约束。

相似题目

题目	难度	考察点
46. 全排列	中等	与本题完全同题，代码可原样提交
47. 全排列 II	中等	元素可重复，需排序后加「前一个相同值未使用则跳过」的同层去重
LCR 084. 全排列 II	中等	与 47 同题，是本题去掉「元素互不相同」前提后的直接升级
60. 排列序列	困难	只要第 `k` 个排列，需用阶乘逐位定位而非枚举全部，否则必然超时
784. 字母大小写全排列	中等	每个字母位二选一、数字位无分支，是「每位独立选择」而非重排
剑指 Offer 38. 字符串的排列	中等	对象换成字符且含重复字符，等价于 47 的字符串版
面试题 08.07. 无重复字符串的排列组合	中等	与本题同构，只是把 `int[]` 换成 `String`，返回 `String[]`
面试题 08.08. 有重复字符串的排列组合	中等	字符串版的 47，考察点仍是重复字符的同层去重
78. 子集	中等	顺序无关且长度不定，循环起点回到 `u`，可对照体会排列与子集的差异