LeetCode 第 78 题：子集（Subsets）

题目描述

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

示例：

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

解题思路

子集问题需要找出所有可能的组合，包括空集和自身。由于元素互不相同，我们不需要考虑去重。核心思路是逐个考虑每个元素，决定是否将其加入当前子集，通过递归或迭代生成所有组合。

方法一：回溯法（递归）

回溯法通过深度优先搜索（DFS）遍历所有选择路径。

步骤详解：

1. 定义回溯函数：

   • 参数：当前索引 start（表示从数组的哪个位置开始选择）、当前子集 path。
   • 功能：从 start 开始遍历数组，将元素加入 path，递归处理后续元素，再回溯移除当前元素。

2. 递归过程：

   • 每进入一层递归，先将当前 path 加入结果集（确保所有子集都被记录）。
   • 遍历 start 之后的元素，依次加入 path 并递归，递归完成后回溯。

3. 示例推导（nums = [1,2,3]）：

   • 初始：path = []，加入结果集 [[]]。
   • 第一层：选择 1，path = [1]，加入结果集 [[], [1]]；递归处理剩余元素 [2,3]。
   • 第二层：选择 2，path = [1,2]，加入结果集；递归处理 [3]。
   • 第三层：选择 3，path = [1,2,3]，加入结果集；回溯到 [1,2]，再回溯到 [1]。
   • 继续选择 3，path = [1,3]，加入结果集；回溯到 [1]，再回溯到 []。
   • 同理处理以 2 和 3 开头的子集。

4. 代码实现：

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

方法二：迭代法（位运算思想）

每个元素有“选”或“不选”两种状态，子集总数应为 \(2^n\)（n 为数组长度）。通过循环模拟所有组合。

步骤详解：

1. 初始化结果集：包含空集 [[]]。

2. 遍历每个元素：

   • 对于当前元素，将已存在的所有子集复制一份，并在每个复制子集中加入当前元素。
   • 将新生成的子集加入结果集。

3. 示例推导（nums = [1,2,3]）：

   • 初始：res = [[]]
   • 处理元素 1：复制所有子集 []，加入 1 得到 [1]，更新 res = [[], [1]]。
   • 处理元素 2：复制子集 [] 和 [1]，分别加入 2 得到 [2], [1,2]，更新 res = [[], [1], [2], [1,2]]。
   • 处理元素 3：复制所有子集并加入 3，得到 [3], [1,3], [2,3], [1,2,3]，最终结果包含 8 个子集。

4. 代码实现：

def subsets(nums):
    res = [[]]
    for num in nums:
        new_subsets = [subset + [num] for subset in res]
        res += new_subsets
    return res

总结

• 回溯法：通用性强，适合需要逐步构建解的场景，通过递归和回溯覆盖所有可能性。
• 迭代法：直观高效，利用子集的数量规律逐步扩展，适合理解组合生成的过程。
• 时间复杂度：两种方法均为 \(O(2^n)\)，因为需要生成所有子集。空间复杂度为 \(O(n)\)（递归栈或临时存储）。