LeetCode 90. 子集 II

约 6 分钟
文章信息 7 个分类 5 个标签
分类
LeetCode CodeTop 中等 未解决 5-10 字节跳动 微软
标签
数组 位运算 回溯 回溯经典题 子集问题
目录

题目描述

✅ 90. 子集 II

image-20250419040251029

题意分析

输入是一个整数数组，其中允许出现重复元素，要求返回它的所有子集（幂集），并且结果里不能有两个相同的子集。子集之间的顺序、子集内部元素的顺序都不作要求。

关键在于「相同」的判定标准：两个子集只要元素的多重集合一致就算重复，与它们由原数组的哪些下标构成无关。例如 [1,2,2] 里下标 1 的 2 和下标 2 的 2 各自单独成集时，是同一个子集 [2]，只能保留一份。

反过来，同一个值在一个子集里出现多次是完全合法的：[2,2] 用掉了两个不同下标上的 2，它与 [2] 是不同的子集，必须都出现在答案里。这条和上一条的区别是本题最容易含混的地方。

约束里数组长度不超过 10，子集总数最多 $2^{10}$，规模很小，说明预期解法就是把所有子集枚举出来，重点考的是去重而不是效率。边界上要覆盖：空集永远属于答案；数组元素全部相同时答案是 n + 1 个子集；数组无重复时答案就是普通幂集。

解法：排序 + 回溯跳过同层重复

核心思路

普通子集问题按下标做选择；本题有重复值，不同下标可能表示同一个选择。若先枚举 $2^n$ 个下标集合再用哈希表去重，虽然可行，却会先生成重复答案。更直接的办法是在搜索树上剪掉重复分支。

先排序，使相同值相邻。backtrack(start) 表示下一次只能从下标 start 以后选择，当前 path 已经是一个合法子集，因此进入递归就把它的副本加入答案。枚举本层候选 i 时，若 i > start && nums[i] == nums[i - 1]，说明同一层已经用前一个相同值展开过，当前分支必然重复，直接跳过。

去重条件必须是 i > start，不能写成 i > 0。前者只跳过同层重复；当 i == start 时，即使它和前一个元素相同，也表示上一层已经选过一个同值元素，本层继续选第二个是合法的，因此 [2,2] 不会被误删。

正确性可以从两方面说明：

  • 不重复：同一层的一段相同值只保留最左边的候选，所以不会出现两个以相同路径、相同下一值开头的分支。
  • 不遗漏：任意合法子集都可以按排序后的值表示；若某个值需要选 $k$ 次，搜索会依次选择这段相同值中最靠左的 $k$ 个下标。被跳过的只是等价下标，不是新的取值次数。

因而搜索树中的每个节点恰好对应一个不同子集。

解题步骤

  1. 对 nums 排序，让重复值相邻。
  2. 从 backtrack(0) 开始；每次进入递归，先复制 path 加入答案，空集也会在根节点被收集。
  3. 从 start 开始枚举候选：若当前值和本层前一个候选相同，则跳过。
  4. 选择 nums[i] 后递归到 i + 1，保证每个下标最多使用一次。
  5. 递归返回后弹出刚加入的值，恢复现场，再尝试下一个候选。

以 [1,2,2] 为例：根节点只允许第一个 2 作为本层分支的起点，因此 [2] 不会生成两次；进入该分支后，第二个 2 是新一层的第一个候选，仍可被选择，于是 [2,2] 被保留。最终得到 []、[1]、[1,2]、[1,2,2]、[2]、[2,2]。

代码实现

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), res);
        return res;
    }

    private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
        res.add(new ArrayList<>(path));
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }

            path.add(nums[i]);
            backtrack(nums, i + 1, path, res);
            path.remove(path.size() - 1);
        }
    }
}

import "sort"

func subsetsWithDup(nums []int) [][]int {
    sort.Ints(nums)
    res := make([][]int, 0)
    path := make([]int, 0)
    var backtrack func(start int)
    backtrack = func(start int) {
        cur := append([]int{}, path...)
        res = append(res, cur)
        for i := start; i < len(nums); i++ {
            if i > start && nums[i] == nums[i-1] {
                continue
            }

            path = append(path, nums[i])
            backtrack(i + 1)
            path = path[:len(path)-1]
        }
    }
    backtrack(0)
    return res
}

复杂度分析

设不同子集的长度总和为 $S$。

  • 时间复杂度：排序为 $O(n \log n)$，搜索和复制答案为 $O(S)$；最坏情况下元素互不相同，$S = O(n \cdot 2^n)$，因此总时间复杂度为 $O(n \cdot 2^n)$。
  • 空间复杂度：不计返回结果为 $O(n)$，来自递归栈和路径；返回结果本身占 $O(S)$，最坏为 $O(n \cdot 2^n)$。

关键点总结

  • 排序的目的不是改变答案顺序，而是让相同值相邻，从而用一个局部条件完成去重。
  • i > start 限定了去重作用域：同层只能选一个分支代表，跨层仍能继续选相同值。
  • 子集题的每个搜索节点都是答案；组合和排列题则常常只在满足终止条件时收集。
  • path 是复用的可变对象，存入结果前必须复制。
  • 代码会原地排序输入；若调用方要求保留原数组，应先复制再排序。

易错点总结

  • 去重写成 i > 0 && nums[i] == nums[i - 1]：会跨层跳过重复值，[2,2] 这类合法子集随之丢失。
  • 未排序就比较相邻元素：例如 [2,1,2] 中两个 2 不相邻，重复分支无法被识别。
  • 写成 res.add(path) 或直接追加 path：所有答案共享同一个容器，回溯后内容会一起改变。
  • 递归参数传 start + 1 而不是 i + 1：下一层可能再次选择当前下标，生成非法结果。
  • 忘记撤销选择：兄弟分支会继承上一个分支的元素；只在叶子收集答案则会漏掉空集和中间节点对应的子集。

相似题目

题目 难度 考察点
78. 子集 中等 无重复元素的幂集，可对照二进制枚举写法
40. 组合总和 II 中等 同样是同层去重，但只在和等于目标时收集答案
47. 全排列 II 中等 排列场景的去重，需要配合 used 数组判断前一个同值是否已用
491. 非递减子序列 中等 不能排序，只能用本层的哈希集合记录已用过的值
LCR 079. 子集 中等 与 78 同题，适合先写无重复版再改造成本题
面试题 08.04. 幂集 中等 幂集的另一处出题，可练习迭代式逐元素扩展的写法