LeetCode LCR 079. 子集

约 8 分钟
文章信息 5 个分类 4 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
数组 LCR 位运算 回溯
目录

题目描述

✅ LCR 079. 子集

题意分析

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

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

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

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

解法：回溯枚举下一个选择位置

核心思路

最朴素的想法是「每个元素选或不选」，于是要写 n 重嵌套循环。但 n 是运行时才知道的，固定层数的循环写不出来——需要一种能表达「层数不定的嵌套循环」的机制，那就是递归。

另一种朴素做法是枚举 0 到 $2^n - 1$ 的二进制掩码，第 i 位为 1 就取 nums[i]。它本身是对的，但把「做选择」这件事藏进了位运算里，一旦题目变成「元素有重复要去重」或「和超过上限就剪枝」，掩码写法就无处下手。所以主解要保留显式的选择过程。

关键观察是：一个子集与「它的元素按下标升序排好的那个序列」一一对应。既然如此，只要规定「新元素的下标必须严格大于已选的所有下标」，每个子集就只会被生成一次。于是决策树长成这样：根是空集，节点 path 的分支是「从 start、start+1、…、n-1 里挑一个作为下一个元素」，挑了 nums[i] 就进入 start = i + 1 的子节点。这棵树的每个节点（包括根）都恰好对应一个子集，节点总数就是 $2^n$。

递归不变量是：进入 backtrack(start) 时，path 里的下标严格递增，且全部小于 start。它保证了两件事——path 当前就是一个合法子集，可以立刻收集；以及后续选择只在 [start, n) 里，不会回头，因此不会生成同一集合的第二种排列。

path 是一个被所有递归层共享的可变缓冲区，用来代表「当前所在的树节点」。进入子节点前追加元素，从子节点返回后必须删掉这个元素，同一层的下一个兄弟分支才能看到和进入本层时完全一样的状态——这就是「撤销选择」的全部意义。

也正因为 path 一直在被改写，收集答案时必须拍一份快照（new ArrayList<>(path)）。直接把 path 的引用放进结果集，等递归全部结束、path 被逐层弹空之后，结果集里的每一项都会指向同一个空列表。

解题步骤

  • 准备结果集 res 与共享路径 path，从 backtrack(0) 开始。传 0 表示第一次选择可以从任意下标开始。
  • 每进入一层，先无条件地把 path 的快照放进 res。因为不变量保证此刻 path 已经是一个合法子集，而且答案分布在树的每个节点上，不是只在叶子上。
  • 从 i = start 遍历到 n - 1，依次把 nums[i] 当作「下一个加入的元素」。循环变量的下界是 start，这是不回头的来源。
  • 追加 nums[i] 后递归进入 backtrack(i + 1)。传 i + 1 是因为每个元素最多用一次，下一层不能再看到 i 及其左边的下标。
  • 递归返回后删掉刚追加的元素，把 path 还原成进入本层时的样子，再继续下一个 i。
  • 以 nums = [1,2,3] 走一遍（缩进表示递归深度，箭头后是这一步收集到的子集）：
  • backtrack(0)，path = [] → 收集 []。
  • 　i = 0：path = [1] → backtrack(1) → 收集 [1]。
  • 　　i = 1：path = [1,2] → backtrack(2) → 收集 [1,2]。
  • 　　　i = 2：path = [1,2,3] → backtrack(3) → 收集 [1,2,3]；循环为空，返回后 path 撤销回 [1,2]。
  • 　　　循环结束，返回前 path 撤销回 [1]。
  • 　　i = 2：path = [1,3] → backtrack(3) → 收集 [1,3]；返回后撤销回 [1]。
  • 　　循环结束，返回前 path 撤销回 []。
  • 　i = 1：path = [2] → backtrack(2) → 收集 [2]。
  • 　　i = 2：path = [2,3] → backtrack(3) → 收集 [2,3]；返回后撤销回 [2]。
  • 　　返回前撤销回 []。
  • 　i = 2：path = [3] → backtrack(3) → 收集 [3]；返回后撤销回 []。
  • 最终 res 依次是 []、[1]、[1,2]、[1,2,3]、[1,3]、[2]、[2,3]、[3]，共 8 个，正好等于 $2^3$。注意 i = 1 这一支之所以能拿到干净的 [2]，完全依赖上一支返回时把 1 撤销掉了。

代码实现

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        backtrack(nums, 0, path, 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++) {
            path.add(nums[i]);
            backtrack(nums, i + 1, path, res);
            path.remove(path.size() - 1);
        }
    }
}

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

    var backtrack func(start int)
    backtrack = func(start int) {
        // 当前路径本身就是一个子集，需要先收集。
        subset := append([]int(nil), path...)
        res = append(res, subset)

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

    backtrack(0)
    return res
}

复杂度分析

  • 时间复杂度：$O(n \cdot 2^n)$。决策树恰好有 $2^n$ 个节点，遍历树本身是 $O(2^n)$；主导项来自每个节点都要复制一份快照，所有子集的长度之和是 $n \cdot 2^{n-1}$，所以总代价是 $O(n \cdot 2^n)$。这个量级与输出规模同阶，无法再优化。
  • 空间复杂度：$O(n)$，不计结果数组。递归栈最深是 n + 1 层（每层至多选一个元素），共享的 path 长度也不超过 n。

关键点总结

  • 答案的收集时机由题目决定，不一定在叶子上。求幂集时每个节点都是答案，所以收集语句放在函数入口、循环之前；求「长度恰好为 k 的组合」时答案只在特定深度，求排列时答案只在叶子。判断标准是「这个节点代表的状态本身是否已经是一个完整答案」。
  • start 参数是组合类枚举去重的通用工具。它把「集合」固定成「下标升序的唯一序列」，从而把同一集合的 k! 种排列压成一种。凡是「答案不区分顺序」的枚举题，都可以先想能不能用一个单向推进的下界参数解决。
  • 共享缓冲区 + 进入前修改 + 返回后还原，是回溯的标准骨架。两种实现方式必须二选一：共享 path 就一定要撤销；每层传一份新副本就不必撤销但要付出复制代价。混着写（共享却不撤销）一定出错。
  • 把可变状态放进结果集之前必须拍快照。判断依据不是「会不会出错」而是「这个对象之后还会不会被改」，subList 之类的视图同样不算快照。
  • 面试视角：开口先讲决策树的形状和「每个节点即一个子集」的收集时机，再讲 start 为什么能去重，最后才写代码，这套顺序比直接默写更能拿分。常见追问有三个：元素有重复时怎么办（引到 90 题的「排序后同层跳过相同值」）、能不能不用递归（答二进制掩码枚举，但说明它不易扩展剪枝，只适合当补充解）、为什么必须拷贝 path。二进制掩码写法可以作为第二解，但不适合当主答案。

易错点总结

  • res.add(path) 直接放引用而不拷贝：nums = [1,2] → 结果集里 4 个元素都指向同一个列表，递归结束时它已被逐层弹空，输出变成 [[],[],[],[]]。
  • 递归时传 start 或 i 而不是 i + 1：nums = [1,2] → backtrack(0) 里选了下标 0 后，下一层仍从下标 0 开始，于是不断重复选择 nums[0]，递归无法收敛，直接栈溢出。
  • 忘掉 path.remove(path.size() - 1)：nums = [1,2,3] → 同层后续分支带着前一分支的残留元素，答案里会出现 [1,2,3,3] 这种长度超过 3 的「子集」，同时 [2]、[3] 等子集再也不会被生成。
  • 只在 start == nums.length 时才收集：nums = [1,2,3] → 只有以下标 2 结尾的路径才会走到那一层，答案只剩 [1,2,3]、[1,3]、[2,3]、[3] 四个，所有不含 3 的子集（含空集）全部丢失。
  • 加一句 if (!path.isEmpty()) 再收集：nums = [1,2,3] → 空集被过滤掉，输出 7 个子集而不是 8 个。
  • Java 里写成 path.remove(nums[i]) 来撤销：nums = [1,2,3] → remove(int) 的语义是按下标删除而不是按值删除，path = [1] 时执行 remove(1) 会抛 IndexOutOfBoundsException。要按值删必须写 path.remove(Integer.valueOf(nums[i]))，但按下标删末位才是正确写法。
  • 用 res.add(path.subList(0, path.size())) 当快照：nums = [1,2] → subList 返回的是原列表的视图而非副本，后续对 path 的修改会同步反映到答案里，并且原列表结构改变后访问该视图还会抛 ConcurrentModificationException。
  • 把「空输入」的答案写成空列表：n = 0 时正确答案是只含空集的 [[]]，返回 [] 会少一个答案；这也是「收集语句必须在循环之前无条件执行」的直接推论。

相似题目

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