LeetCode 78. 子集

约 4 分钟
文章信息 23 个分类 5 个标签
分类
LeetCode CodeTop 中等 已解决 需复习 100-200 字节跳动 微软 美团 阿里巴巴 快手 腾讯 猿辅导 百度 滴滴 华为 拼多多 小米 商汤 旷视 亚马逊 虾皮 LeetCode 热题 100
标签
数组 位运算 回溯 回溯经典题 子集问题
目录

题目描述

✅ 78. 子集

image-20250419035406562

题意分析

输入是一个元素互不相同的整数数组 nums，要求输出它的全部子集（幂集）。子集之间的顺序、子集内部元素的顺序都不做要求，只要求集合意义上不重不漏。

「元素互不相同」这个条件直接决定了不需要任何去重逻辑：任意两个下标集合不同，对应的取值集合也必然不同。

长度为 n 的数组有 $2^n$ 个子集，这就是输出规模的下界，所以题目的数据范围必然很小，也不存在比「把每个子集都造出来」更省的算法。真正要设计的是一个不重不漏的枚举顺序，而不是省时间。

边界情形有三处：空集也是合法子集，必须出现在答案里；单元素数组的答案是两个子集；元素可以是负数，因此不能拿取值本身当下标或标记位。

解法：回溯枚举

核心思路

按下标递增选择元素，path 表示当前子集。每进入一层先保存 path 的副本，再从 start 开始选择下一个元素；递归返回时撤销选择。这样每个子集只会生成一次。

解题步骤

  • 从空路径和 start = 0 开始回溯，先将当前路径加入答案。
  • 枚举 [start, n) 中的下标 i，把 nums[i] 加入路径。
  • 递归处理 i + 1 之后的元素，保证下标递增且元素不会重复使用。
  • 递归返回后删除路径末尾元素，继续尝试同层的下一个选择。

代码实现

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), ans);
        return ans;
    }

    private void backtrack(int[] nums, int start, List<Integer> path,
                           List<List<Integer>> ans) {
        ans.add(new ArrayList<>(path));

        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            backtrack(nums, i + 1, path, ans);
            path.remove(path.size() - 1);
        }
    }
}

func subsets(nums []int) [][]int {
    ans := make([][]int, 0)
    path := make([]int, 0)

    var backtrack func(int)
    backtrack = func(start int) {
        ans = append(ans, append([]int(nil), path...))

        for i := start; i < len(nums); i++ {
            path = append(path, nums[i])
            backtrack(i + 1)
            path = path[:len(path)-1]
        }
    }

    backtrack(0)
    return ans
}

复杂度分析

  • 时间复杂度：$O(n \cdot 2^n)$，共有 $2^n$ 个子集，复制每个子集最多需要 $O(n)$。
  • 空间复杂度：$O(n)$，不计返回结果；递归栈和路径最多包含 n 个元素。

关键点总结

  • 空集也是答案，因此进入每层递归时就收集当前路径。
  • 递归传入 i + 1，用递增下标避免重复枚举。
  • 答案必须保存 path 的副本，共享路径在回溯过程中会继续变化。

易错点总结

  • 直接把 path 引用加入答案，最终所有结果会指向同一个列表。
  • 忘记撤销末尾元素，会让上一分支的状态污染下一分支。
  • 下一层仍从 start 或 i 开始，会重复使用当前元素。
  • 只在叶子节点收集，会漏掉空集和较短的子集。

相似题目

题目 难度 考察点
46. 全排列 中等 答案区分顺序，不能用单向推进的 start，要改成 used 标记且只在叶子收集
77. 组合 中等 只要长度恰好为 k 的子集，收集条件从「每个节点」变成「深度等于 k」，可加剩余量剪枝
90. 子集 II 中等 数组含重复元素，需先排序再在同一层跳过取值相同的分支，本题因元素互不相同省掉了这步
LCR 079. 子集 中等 与本题同题换皮，适合用来检验同一套骨架能否脱稿一次写对
面试题 08.04. 幂集 中等 同样求幂集，但面试中常被追加要求给出二进制掩码枚举作为第二种实现