我来给你讲解 LeetCode 第 78 题「子集」。

题目描述

给你一个整数数组 nums，数组中的元素 互不相同。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

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

示例 2：

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

解题思路分析

关键理解

1. 子集：对于长度为 n 的数组，共有 2ⁿ 个子集（包括空集）
2. 互不相同：意味着不需要考虑去重问题
3. 不能包含重复：每个子集都是唯一的

方法选择

这道题有三种经典解法：

1. 回溯法（递归+剪枝）
2. 迭代法（逐步构建）
3. 位运算法（利用二进制位表示）

我会重点讲解最直观的回溯法。

循序渐进讲解

步骤 1：理解问题本质

子集问题可以看作：对于每个元素，我们都有两种选择：

• 包含这个元素
• 不包含这个元素

比如数组 [1,2,3]：

• 对于元素 1：选或不选
• 对于元素 2：选或不选
• 对于元素 3：选或不选

这样就会产生 2×2×2 = 8 种组合。

步骤 2：回溯法核心思想

回溯法的基本框架：

def backtrack(路径, 选择列表):
    if 满足结束条件:
        结果.append(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

对于子集问题，我们需要稍微调整这个框架。

步骤 3：具体实现思路

1. 定义递归函数：backtrack(start, path)

   • start：当前考虑的元素起始位置
   • path：当前已选择的元素集合

2. 递归过程：

   • 每次递归时，先把当前路径加入结果
   • 从 start 开始遍历剩余元素
   • 对于每个元素：选择它 → 递归 → 撤销选择

3. 终止条件：当 start 超过数组长度时自然结束

步骤 4：详细推演示例

以 nums = [1,2,3] 为例：

第一层递归 (start=0)：

• 路径 [] 加入结果：[[]]
• 遍历 i=0,1,2：
  • 选择 1：路径变为 [1]
  • 进入第二层递归 (start=1)

第二层递归 (start=1, 路径=[1])：

• 路径 [1] 加入结果：[[], [1]]
• 遍历 i=1,2：
  • 选择 2：路径变为 [1,2]
  • 进入第三层递归 (start=2)

第三层递归 (start=2, 路径=[1,2])：

• 路径 [1,2] 加入结果：[[], [1], [1,2]]
• 遍历 i=2：
  • 选择 3：路径变为 [1,2,3]
  • 进入第四层递归

如此继续，最终得到所有子集。

步骤 5：代码实现

def subsets(nums):
    def backtrack(start, path):
        # 每次递归都把当前路径加入结果
        result.append(path[:])
        
        # 从start开始遍历剩余元素
        for i in range(start, len(nums)):
            # 选择当前元素
            path.append(nums[i])
            # 递归处理后续元素
            backtrack(i + 1, path)
            # 撤销选择（回溯）
            path.pop()
    
    result = []
    backtrack(0, [])
    return result

步骤 6：复杂度分析

• 时间复杂度：O(N × 2ⁿ)，每个子集都需要被生成，最坏情况下有 2ⁿ 个子集
• 空间复杂度：O(N)，递归栈的深度为 N

步骤 7：迭代法（备选方案）

迭代法的思路更直接：

def subsets(nums):
    result = [[]]
    for num in nums:
        # 对于每个新元素，把它加入到所有已有子集中
        result += [subset + [num] for subset in result]
    return result

这种方法更容易理解：从空集开始，每次遇到新元素，就把它加入到之前的所有子集中。

总结

子集问题的核心是理解每个元素都有选或不选两种可能。回溯法通过系统性地探索所有选择组合，确保不重不漏地生成所有子集。这种方法可以推广到很多组合问题中。

这个解法你理解了吗？如果有任何疑问，我可以进一步解释某个具体步骤。