我们来学习 LeetCode 第 78 题：子集（Subsets）。

题目描述

给你一个整数数组 nums，数组中的元素 互不相同。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• nums 中的所有元素 互不相同

解题思路

1. 问题分析

子集问题就是求给定集合的所有子集，包括空集和自身。
长度为 n 的数组，子集个数为 2^n。

我们需要枚举所有可能的组合，每个元素在某个子集中只有两种可能：选 或 不选。

2. 方法一：递归（回溯法）

这是最直观的解法，我们可以用 DFS 来遍历所有选择情况。

思路：

• 从第一个元素开始，每一步决定是否将当前元素加入当前子集。
• 当处理完所有元素后，将当前子集加入结果列表。

步骤：

1. 定义结果列表 res 和临时列表 path（记录当前子集）。
2. 定义递归函数 backtrack(start, path)：
   • 将 path 的副本加入 res（每个节点都是子集，不只是叶子节点）。
   • 从 start 索引开始遍历数组：
     • 将 nums[i] 加入 path。
     • 递归调用 backtrack(i + 1, path)。
     • 回溯：从 path 中移除刚才加入的元素。
3. 调用 backtrack(0, [])。
4. 返回 res。

示例 nums = [1,2,3] 的递归树（简化）：

[]
  [1]
    [1,2]
      [1,2,3]
    [1,3]
  [2]
    [2,3]
  [3]

每个节点都加入结果，所以顺序是：
[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]

3. 方法二：迭代枚举（位运算思想）

每个子集可以看作一个二进制位掩码，长度为 n，每一位表示是否选取对应元素。

思路：

• 子集总数 total = 1 << n（即 2^n）。
• 对于每个数 mask 从 0 到 total-1：
  • 根据 mask 的二进制位，选取对应元素加入当前子集。

步骤：

1. n = len(nums)
2. total_subsets = 1 << n
3. 循环 mask 从 0 到 total_subsets - 1：
   • subset = []
   • 循环 i 从 0 到 n-1：
     • 如果 mask 的第 i 位是 1，则将 nums[i] 加入 subset。
   • 将 subset 加入结果列表。

示例 nums = [1,2,3], n=3, total=8：

mask  binary  子集
0    000     []
1    001     [1]
2    010     [2]
3    011     [1,2]
4    100     [3]
5    101     [1,3]
6    110     [2,3]
7    111     [1,2,3]

4. 方法三：迭代构造

另一种迭代方法：从空集开始，每遇到一个新元素，就在之前所有子集中加上该元素，形成新的子集。

步骤：

1. 初始化 res = [[]]
2. 遍历 nums 中每个数 num：
   • 新建列表 new_subsets
   • 对于 res 中每个已有子集 subset：
     • 创建新子集 new_subset = subset + [num]
     • 加入 new_subsets
   • 将 new_subsets 全部加入 res
3. 返回 res

示例 nums = [1,2,3]：

• 初始: [[]]
• 加 1: [] -> [],[1] → [[], [1]]
• 加 2: []->[2], [1]->[1,2] → [[], [1], [2], [1,2]]
• 加 3: 对四个子集分别加 3 → [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

代码实现（回溯法为例）

def subsets(nums):
    res = []
    
    def backtrack(start, path):
        res.append(path[:])  # 添加当前子集
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    
    backtrack(0, [])
    return res

复杂度分析：

• 时间复杂度：O(n × 2^n)，因为共有 2^n 个子集，每个子集平均长度 O(n)。
• 空间复杂度：O(n)，递归栈深度最大为 n。

总结

• 子集问题是经典的组合枚举问题，有三种常见解法：回溯、位掩码、迭代构造。
• 回溯法最通用，易于理解和扩展到有重复元素的情况（需要去重）。
• 位掩码法适用于 n 较小的情况（n ≤ 20 左右）。
• 迭代构造法思路直观，代码简洁。