LeetCode 47. 全排列 II

2026-04-16 HGNULB 约 6 分钟

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

分类

LeetCode CodeTop 中等已解决需加强 50-100 字节跳动微软美团阿里巴巴快手腾讯猿辅导滴滴京东华为小米虾皮图森

题目描述

✅ 47. 全排列 II

题意分析

给定一个可能包含重复数字的数组，要求返回所有不重复的全排列。这正是它与 46 题的唯一差别：46 的输入互不相同，任意两条不同的下标选择路径都对应不同排列；本题输入有重复值，不同的下标路径可能拼出同一个排列——比如 [1,1,2]，两个 1 交换位置后排列看起来一模一样，答案只应保留 [1,1,2]、[1,2,1]、[2,1,1] 三个，而不是 $3! = 6$ 个。

约束信号：数组长度不超过 8，指数级枚举可以接受，但重复分支必须剪掉，否则重复元素多时（如 8 个相同数字）会做大量无用功。

边界上，数组长度至少为 1，不必处理空输入；输出顺序不限，但每个多重集排列只能出现一次。

解法：排序 + used 去重回溯

核心思路

问题关键：排列需要每层都从全部下标中选一个未使用元素；输入有重复值时，不同下标可能生成相同排列。生成全部排列后再用集合去重虽然可行，但重复分支仍会完整搜索。

为什么选排序 + 回溯剪枝：先排序让相同数字相邻，再在同一层只允许相同数字中的第一个可选下标进入递归。这样重复分支在产生时就被剪掉，不需要结果集合去重。

不变量：相同数字必须按排序后的下标从左到右进入当前路径。选择 nums[i] 时，若 nums[i] == nums[i - 1] 且 used[i - 1] == false，说明前一个相同数字没有在当前路径中；此时选择 i 会与本层选择 i - 1 产生同构子树，必须跳过。若 used[i - 1] == true，前一个相同数字已在路径里，选择当前数字合法。

used[i] 解决“同一下标不能重复使用”，去重条件解决“同层相同值不能重复选择”。两者职责不同，缺一不可。该顺序约束让每个不重复排列只对应一条合法下标路径，因此既不重复也不遗漏。

解题步骤

排序数组，使相同数字相邻。

用 used 标记当前路径已使用的下标；每一层仍从 0 到 n - 1 枚举。

跳过已使用下标；再用 i > 0 && nums[i] == nums[i - 1] && !used[i - 1] 剪掉同层重复分支。

选择当前数字、递归下一层，返回后撤销路径和 used 状态。

路径长度等于 n 时复制一份加入答案。

以 [1a,1b,2] 为例：根节点先选择 1a 并搜索完其子树；回到根节点后考虑 1b，此时 used[1a] = false，说明它与刚才的 1a 属于同层重复选择，直接剪枝。但在路径已经包含 1a 时，used[1a] = true，此时允许继续选择 1b。

代码实现

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;
        }
    }
}

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 数组；不计返回结果。

关键点总结

去重模板是“排序 + 同层跳过相邻重复值”；排列额外需要 used，组合/子集通常使用起点下标。

!used[i - 1] 的本质是给相同元素规定唯一使用顺序，而不是简单地“看到相同数字就跳过”。

收集答案时必须复制路径；路径是所有递归层共享并反复修改的对象。

面试时要能区分路径内去重与同层去重，并用 [1,1,2] 解释剪枝条件。

易错点总结

不排序就比较相邻元素无法去重。反例 [1,2,1]：两个 1 不相邻，会生成重复排列。

去重条件不能省略 !used[i - 1]；若相邻相等就无条件跳过，[1,1,2] 中第二个 1 永远无法进入路径。

res.add(path) 或 Go 的 append(res, path) 都没有复制底层数据，后续回溯会改坏已收集结果。

递归返回后必须同时撤销路径和 used；只恢复其中一个都会污染兄弟分支。

只在结果阶段用集合去重会保留全部重复搜索，例如 8 个相同数字仍会遍历 $8!$ 条路径。

相似题目

题目	难度	考察点
46. 全排列	中等	无重复元素的排列回溯基础模板
60. 排列序列	困难	不枚举全排列，用阶乘计数直接定位第 k 个
784. 字母大小写全排列	中等	每个位置独立二选一，不换位的枚举变体
LCR 083. 全排列	中等	46 的镜像题，巩固 used 数组回溯写法
LCR 084. 全排列 II	中等	本题镜像，重写一遍同层去重条件
剑指 Offer 38. 字符串的排列	中等	去重排列在字符串上的应用
面试题 08.07. 无重复字符串的排列组合	中等	字符版无重复排列，练模板迁移
面试题 08.08. 有重复字符串的排列组合	中等	字符版含重复排列，同层去重再实践