子集-LeetCode

78. 子集 - Subsets

🎯 问题描述（来源于LeetCode）

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

说明：

• 子集包括空集和原集合本身。

示例：

• 示例 1：

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

• 示例 2：

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

💻 解题思路

思路一：枚举“选哪个”（组合型回溯）

算法步骤

1. 获取数组长度 n，初始化结果列表 ans 和当前路径列表 path。
2. 定义递归函数 dfs(i)，表示当前考虑从下标 i 开始的元素进行选择：
   • 首先将当前 path 的副本加入 ans（对应“不选后面的任何元素”）。
   • 然后从 i 到 n-1 遍历元素：将 nums[j] 加入 path，递归调用 dfs(j+1)，然后弹出 path 最后一个元素（回溯）。
3. 从 dfs(0) 开始搜索。
4. 返回 ans。

思路一：代码实现

from typing import List

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        ans = []
        path = []

        def dfs(i: int) -> None:
            ans.append(path.copy())   # 不选，把当前子集加入答案
            for j in range(i, n):     # 选，枚举选择的数字
                path.append(nums[j])
                dfs(j + 1)
                path.pop()

        dfs(0)
        return ans

---

思路二：枚举“选或不选”（分治回溯）

算法步骤

1. 获取数组长度 n，初始化结果列表 ans 和当前路径列表 path。
2. 定义递归函数 dfs(i)，表示处理第 i 个元素（下标从 0 开始）：
   • 如果 i == n，说明已经对所有元素做出了选择，将当前 path 的副本加入 ans，返回。
   • 不选 nums[i]：直接递归调用 dfs(i+1)。
   • 选 nums[i]：将 nums[i] 加入 path，递归调用 dfs(i+1)，然后弹出 path 最后一个元素（回溯）。
3. 从 dfs(0) 开始搜索。
4. 返回 ans。

思路二：代码实现

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        ans = []
        path = []

        def dfs(i: int) -> None:
            if i == n:                     # 子集构造完毕
                ans.append(path.copy())
                return
            # 不选 nums[i]
            dfs(i + 1)
            # 选 nums[i]
            path.append(nums[i])
            dfs(i + 1)
            path.pop()                     # 恢复现场

        dfs(0)
        return ans

📊 性能分析

• 时间复杂度：$O(n \times 2^n)$，共 $2^n$ 个子集，每个子集复制需要 $O(n)$ 时间。
• 空间复杂度：$O(n)$，递归栈深度为 $n$，加上路径数组 path 的空间。

思考

• 两种思路都是经典的回溯解法。思路一（枚举选哪个）在递归过程中每次先加入当前子集，然后遍历可选的元素，适合需要按顺序构造子集的场景。思路二（选或不选）更直观地模拟了每个元素是否加入子集的过程，递归树是满二叉树，更容易理解。
• 注意：无论哪种写法，都不能直接 append(path)，必须复制一份（path.copy() 或 path[:]），因为 path 是可变对象，后续回溯修改会影响已存入的结果。
• 本题也可用二进制枚举法（迭代）实现，但回溯法更具通用性，能轻松扩展到组合、排列等问题。