LeetCode 47. 全排列 II

约 6 分钟
文章信息 22 个分类 3 个标签
分类
LeetCode CodeTop 中等 已解决 需加强 50-100 腾讯 字节 阿里 华为 微软 美团 京东 小米 百度 网易 快手 滴滴 虾皮 招行 猿辅导 图森
标签
数组 排序 回溯

题目描述

✅ 47. 全排列 II

image-20260928194837233

题意分析

返回数组元素能组成的所有不同排列，每条排列都必须使用全部输入元素且每个下标恰好使用一次。不同位置可以存放相同值，但交换两个相同值不会产生新排列，结果中只能保留一份。

排列区分元素顺序，答案列表本身可以按任意顺序返回。不能先把输入数组去重，因为每种数值的出现次数必须保留；需要同时处理“下标不能重复使用”和“最终数值序列不能重复”两个要求。

解法：排序 + used 去重回溯

核心思路

[!blue]

用 path 保存已经填好的排列前缀，一层递归决定下一个位置放什么。因为排列允许任意顺序，每层都要从整个数组中选择，而不能只枚举后面的下标；used[i] 表示下标 i 是否已经放入当前路径，保证同一元素不会被复用。

仅靠 used 仍会重复：相等值来自不同下标，交换它们的选择顺序会得到相同的数值序列。先排序使相等值相邻，再规定这些相等元素只能按下标从小到大的顺序进入路径。

因此，当 nums[i] == nums[i - 1] 且 used[i - 1] 为假时，不能选择 i。前一个相等元素尚未进入当前前缀，先选它就能覆盖先选 i 所能生成的全部数值排列，当前分支没有必要重复搜索。

若前一个相等元素已经在路径中，则可以继续使用当前元素：此时是在同一排列的后续位置放入另一个相同值，并不是重复生成整个排列。这就是条件必须包含 !used[i - 1] 的原因。

任意一个合法的数值排列，都能把其中同值元素依出现先后映射到排序后递增的下标，因此上述限制不会漏解；同值下标的次序又被唯一确定，所以不会重复。路径长度达到 n 时复制保存，随后撤销本轮选择和标记，让其他分支从相同前缀继续搜索。

解题步骤

  1. 排序数组，使相同数字相邻。
  2. 用 used 标记当前路径已使用的下标；每一层仍从 0 到 n - 1 枚举。
  3. 跳过已使用下标；再用 i > 0 && nums[i] == nums[i - 1] && !used[i - 1] 剪掉同层重复分支。
  4. 选择当前数字、递归下一层，返回后撤销路径和 used 状态。
  5. 路径长度等于 n 时复制一份加入答案。

代码实现

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

        dfs(nums, used, new ArrayList<>(), res);

        return res;
    }

    private void dfs(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));

            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }

            // 前一个相等元素未在路径中时，当前选择属于同层重复。
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue;
            }

            used[i] = true;
            path.add(nums[i]);
            dfs(nums, used, path, res);
            // 路径与使用标记一起撤销，让兄弟分支从相同状态出发。
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

import "sort"

func permuteUnique(nums []int) [][]int {
    sort.Ints(nums)
    res := make([][]int, 0)
    path := make([]int, 0, len(nums))
    used := make([]bool, len(nums))

    var dfs func()
    dfs = func() {
        if len(path) == len(nums) {
            perm := append([]int(nil), path...)
            res = append(res, perm)
            return
        }

        for i := 0; i < len(nums); i++ {
            if used[i] {
                continue
            }
            // 前一个相等元素未在路径中时，当前选择属于同层重复。
            if i > 0 && nums[i] == nums[i-1] && !used[i-1] {
                continue
            }

            used[i] = true
            path = append(path, nums[i])
            dfs()
            // 路径与使用标记一起撤销，让兄弟分支从相同状态出发。
            path = path[:len(path)-1]
            used[i] = false
        }
    }

    dfs()
    return res
}

复杂度分析

  • 时间复杂度：最坏为 $O(n \times n!)$。元素互不相同时共有 $n!$ 个结果，每个结果复制路径需要 $O(n)$；排序的 $O(n \log n)$ 被该项覆盖。
  • 空间复杂度：$O(n)$，用于递归栈、路径和 used 数组；不计返回结果。

关键点总结

[!green]

  • 去重模板是“排序 + 同层跳过相邻重复值”；排列额外需要 used，组合/子集通常使用起点下标。
  • !used[i - 1] 的本质是给相同元素规定唯一使用顺序，而不是简单地“看到相同数字就跳过”。
  • 收集答案时必须复制路径；路径是所有递归层共享并反复修改的对象。

易错点总结

[!yellow]

  • 不排序就比较相邻元素，无法识别被其他数值隔开的重复元素，会生成重复排列。
  • 去重条件不能省略 !used[i - 1]；若相邻相等就无条件跳过，同值元素中只有第一个能进入路径，无法用完全部输入元素。
  • res.add(path) 或 Go 的 append(res, path) 都没有复制底层数据，后续回溯会改坏已收集结果。
  • 递归返回后必须同时撤销路径和 used；只恢复其中一个都会污染兄弟分支。
  • 只在结果阶段用集合去重，仍会搜索所有等值下标互换形成的重复分支；应在选择下一项时直接剪掉这些分支。

相似题目

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