LeetCode LCR 084. 全排列 II

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

题目描述

✅ LCR 084. 全排列 II

image-20260929005946269

题意分析

数组可以包含重复值，要求每个下标的元素恰好使用一次，并返回所有不同的值排列，顺序不限。相同值交换下标不会改变排列内容，因此不能把每种下标顺序都当作不同答案。

先按普通排列的方式逐位选择未用元素，再给同值元素规定一种固定的使用次序：排序后，按下标从左到右取用。这样同一个值排列只保留一种下标实现，无需在输出后再去重。

解法：排序与 used 去重排列

核心思路

[!blue]

u 表示下一位要填的位置，path 的前 u 位已经确定，used[i] 表示下标 i 是否在当前排列前缀中。每一层从全部下标中选择下一项，已经使用的下标不能再次选择。

排序使相同值相邻。若 nums[i] == nums[i-1] 且前一个下标尚未使用，当前下标也不允许使用，即跳过 i > 0 && nums[i] == nums[i-1] && !used[i-1]。由此每组同值元素中，已经使用的下标始终构成一个从左开始的前缀。

这条限制不会漏掉任何值排列：对任意合法值序列，把其中某个值的第一次出现分配给该组第一个下标，第二次出现分配给第二个下标，依次类推，就得到一条符合规则的搜索路径。这样的下标分配又是唯一的，所以同一个值排列不会重复生成。

当前一个同值下标已经使用时，后一个仍是独立的可用元素，可以继续选入；否则就无法在一个排列中用完多个相同值。!used[i-1] 只说明它当前不在路径里，不能解释成它历史上一定已经访问过或刚被撤销。

选入元素后递归填下一位，返回时撤销本次选择。u == n 时全部下标都已使用，保存路径快照。Java 的路径长度会变化，需要弹出末尾；Go 的路径固定长为 n，每层只覆盖 path[u]，因此只需恢复 used，旧位置内容会在以后覆盖。

解题步骤

  1. 排序数组，准备结果、路径和按下标记录的 used。
  2. 从 u = 0 开始递归；u == n 时复制当前排列并返回。
  3. 枚举所有下标，跳过已用元素和不符合同值取用次序的元素。
  4. 标记当前元素并填入路径，递归到 u+1，返回后恢复本层的选择状态。

代码实现

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

        // 排序让相同值相邻，是去重条件成立的前提。
        Arrays.sort(nums);
        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) {
            res.add(new ArrayList<>(path));

            return;
        }

        for (int i = 0; i < n; ++i) {
            // used[i]：该下标已用；后半段：同组相同值必须从左往右依次取用。
            if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
                continue;
            }

            path.add(nums[i]);
            used[i] = true;
            dfs(u + 1, n, nums, used, path, res);
            used[i] = false;
            path.remove(path.size() - 1);
        }
    }
}

import (
    "sort"
)

func permuteUnique(nums []int) [][]int {
    n := len(nums)
    res := make([][]int, 0)
    // path 预分配定长，按位赋值，不需要显式撤销。
    path := make([]int, n)
    used := make([]bool, n)
    // 排序让相同值相邻，是去重条件成立的前提。
    sort.Ints(nums)
    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
    }
    for i := 0; i < n; i++ {
        // used[i]：该下标已用；后半段：同组相同值必须从左往右依次取用。
        if used[i] || (i > 0 && nums[i] == nums[i-1] && !used[i-1]) {
            continue
        }
        path[u] = nums[i]
        used[i] = true
        dfs(u+1, n, nums, used, path, res)
        used[i] = false
    }
}

复杂度分析

  • 时间复杂度：最坏上界 $O(n\cdot n!)$；同层去重减少重复分支，但每层仍扫描 n 个位置，不能只凭不同答案条数推断实际访问量。
  • 空间复杂度：路径、used 和递归栈辅助空间 $O(n)$，结果按实际输出规模另计。

关键点总结

[!green]

  • used 记录当前路径，不记录搜索历史；每组相同值按下标从左到右取用是本实现选择的唯一代表顺序。
  • 去重只消除同值元素交换下标带来的重复，不会禁止一个排列同时包含多个相同值。
  • 全部元素相同时只有一个值排列；全部不同则保留普通全排列的所有路径。
  • 排序会修改输入数组，路径存入答案时仍要复制，避免后续回溯改写已有结果。

易错点总结

[!yellow]

  • 先排序，使相同值相邻；当前用 !used[i-1] 约束同值按从左到右顺序选取。
  • 同层跳过重复值，不等于禁止同一路径使用多个相同值。
  • 路径和 used 都要恢复，保存答案时复制；当前去重条件规定相同值按下标从左向右使用。

相似题目

题目 难度 关联与区别
46. 全排列 中等 不含重复值时无需同层去重，本题排序后按相同元素的使用次序剪枝。
90. 子集 II 中等 同样通过排序和选择顺序消除重复结果，但子集与排列对元素顺序的要求不同。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/96904022
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！