LeetCode 90. 子集 II

约 5 分钟
文章信息 7 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 5-10 字节 微软
标签
数组 位运算 回溯

题目描述

✅ 90. 子集 II

image-20260928235216546

题意分析

返回数组的所有不同子集，空集也算答案。每个下标最多使用一次，但输入中的多个同值元素可以同时选入；两个子集是否相同只看所选值及其数量，不看这些值来自哪些下标。

从左到右选择下标，可以避免把同一组元素的不同排列重复输出。输入还有重复值，所以需要先排序，让相同值相邻，再在同一个前缀下只展开一次相同的下一步选择。

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

核心思路

[!blue]

path 保存当前已选元素，start 是下一次允许选择的最小下标。每次进入 backtrack 时，当前 path 本身就是一个合法子集，先复制到 res；随后再枚举后续元素，把当前子集扩展成更长的子集。因此根节点收集空集，中间节点也要收集，不必等到叶子。

对同一个 start，循环中的各个 i 都在同一条 path 后添加一个元素，是同层的候选分支。排序后，若 i > start 且 nums[i] == nums[i-1]，当前选择与前一个同值选择产生相同前缀；而前一个下标更早，后面可选的元素只会更多，所以当前分支能生成的值组合已经被前一个分支覆盖，可以跳过。

去重只针对同层。选中 nums[i] 后递归到 i+1，新一层仍可选择下一个同值元素，因为它是另一个可用下标。这样既允许一个子集中出现多个相同值，又让每种取值数量只沿最靠前的一组同值下标生成一次，不重不漏。

递归返回后移除刚选的元素，恢复本层原来的前缀；保存答案时必须复制，避免后续修改 path 改写已经记录的子集。start 随选择严格增大，到达数组末尾时循环自然结束。

解题步骤

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

代码实现

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)$，搜索需枚举候选并复制答案；最坏情况下元素互不相同，$S = O(n \cdot 2^n)$，因此总时间复杂度为 $O(n \cdot 2^n)$。
  • 空间复杂度：不计返回结果为 $O(n)$，来自递归栈和路径；返回结果本身占 $O(S)$，最坏为 $O(n \cdot 2^n)$。

关键点总结

[!green]

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

易错点总结

[!yellow]

  • 去重写成 i > 0 && nums[i] == nums[i - 1]：会跨层跳过重复值，导致子集中无法保留多个同值元素。
  • 未排序就比较相邻元素：相同值可能分散在数组中，重复分支无法被识别。
  • 写成 res.add(path) 或直接追加 path：所有答案共享同一个容器，回溯后内容会一起改变。
  • 递归参数传 start + 1 而不是 i + 1：下一层可能再次选择当前下标，生成非法结果。
  • 忘记撤销选择：兄弟分支会继承上一个分支的元素；只在叶子收集答案则会漏掉空集和中间节点对应的子集。
  • 输入全部相同时，也要分别保留选择零个、一个直到全部元素的子集；同层去重不能变成删除输入中的重复元素。

相似题目

题目 难度 关联与区别
78. 子集 中等 原题元素互异，本题排序后跳过同层重复选择，保证每个值组合只生成一次。
40. 组合总和 II 中等 同样处理重复值并限制每个下标使用一次，原题额外筛选目标和。
39. 组合总和 中等 在选择和撤销之间枚举组合；本题排序后跳过同层重复值，该题允许同一候选被多次选取。
216. 组合总和 III 中等 在选择和撤销之间枚举组合；本题排序后跳过同层重复值，该题固定元素数量且只取一到九。
77. 组合 中等 在选择和撤销之间枚举组合；本题排序后跳过同层重复值，该题只约束选择数量。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/60066745
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！