LeetCode LCR 083. 全排列

约 5 分钟
文章信息 5 个分类 3 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
数组 LCR 回溯

题目描述

✅ LCR 083. 全排列

image-20260929005941198

题意分析

返回互不相同的数组元素组成的所有排列。每个排列都要使用全部元素且每个位置只用一次，选取顺序不同就是不同答案；各个答案的返回顺序不限。

解法：used 标记枚举排列

核心思路

[!blue]

按排列的位置逐层选择。递归参数 u 表示接下来要填第几个位置，used[i] 表示下标 i 的元素是否已经放进当前排列前缀。本层遍历所有下标，只选择尚未使用的元素，再递归填写下一位。

排列需要保留不同顺序，所以每层都从下标 0 枚举，不能像组合那样只向更大的下标推进。元素互不相同，每个下标排列都对应唯一的值排列；枚举全部未使用下标，就能得到全部 $n!$ 个答案。

Java 用可变列表保存当前路径，选择时追加元素并标记 used，返回后同时撤销末项和标记。Go 将 path 预先分配为长度 n，直接写入 path[u]；它只需撤销 used，因为下一分支会覆盖当前位，尚未填写的后缀不会被用来判断。

u == n 时所有位置都已填好，复制整个路径保存答案。必须保存独立副本，不能让后续回溯覆盖已有结果。

解题步骤

  1. 创建结果、路径和全为 false 的 used 数组，从 u = 0 开始。
  2. 若 u == n，复制当前排列加入结果并返回。
  3. 遍历所有下标，跳过 used[i] 为真的元素。
  4. 将 nums[i] 放到当前位，标记为已用，递归填写第 u + 1 位。
  5. 返回后恢复 used[i]；Java 还要删除刚追加的路径末项。

代码实现

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\cdot n!)$。共有 $n!$ 个完整排列，每个复制 n 个元素；所有内部状态扫描候选的开销也在同一上界内。
  • 空间复杂度：不计结果为 $O(n)$，用于递归栈、路径和 used；结果需要 $O(n\cdot n!)$ 空间。

关键点总结

[!green]

  • used 只描述当前路径中已经使用的位置，不是全局访问标记。
  • 排列要枚举所有未用位置，组合才通过递增起点消除顺序。
  • 追加式路径需要删除末项；定长数组按位置覆盖时，只需保证收集前每一位都已填写。

易错点总结

[!yellow]

  • 每层不能限制只选更大的下标，否则会遗漏不同排列顺序。
  • 返回后必须恢复 used，让同一个元素能在其他排列中再次使用。
  • Java 要同步撤销路径末项；Go 的定长路径不用清空后缀，后续递归会覆盖它。
  • 题目元素互异，不需要按值去重；保存答案时仍必须复制路径。

相似题目

题目 难度 关联与区别
47. 全排列 II 中等 同样逐位置选择未使用元素，原题允许重复值，需要额外限制同层等价选择。
31. 下一个排列 中等 本题一次枚举所有排列，原题只生成字典序紧邻的下一种排列。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/81384266
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！