78. 子集

题目链接（中等）

题目描述

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

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

数据范围：

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

示例

示例 1：

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

示例 2：

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

方法一：位运算枚举

思路及解法

原序列中每个元素只有两种状态：在子集中 或 不在子集中。用一个长度为 n 的 0/1 序列表示，第 i 位为 1 表示 nums[i] 在子集中。

所有 0/1 序列正好对应二进制数 0 到 2^n - 1，因此枚举 mask ∈ [0, 2^n - 1]，对每个 mask，取所有二进制位为 1 的下标对应的元素，就得到一个子集。

举例：n = 3，nums = [5, 2, 9]

0/1 序列	子集	二进制数
000	{}	0
001	{9}	1
010	{2}	2
011	{2,9}	3
100	{5}	4
101	{5,9}	5
110	{5,2}	6
111	{5,2,9}	7

代码

class Solution:
    def subsets(self, nums: list[int]) -> list[list[int]]:
        n = len(nums)
        ans = []
        for mask in range(1 << n):
            subset = []
            for i in range(n):
                if mask & (1 << i):
                    subset.append(nums[i])
            ans.append(subset)
        return ans

复杂度分析

• 时间复杂度：$O(n \times 2^n)$，共 $2^n$ 个状态，每个状态构造子集需 $O(n)$。
• 空间复杂度：$O(n)$，临时数组的开销。

方法二：回溯（选或不选）

思路及解法

原序列的每个元素都有「选」和「不选」两种状态。用递归函数 dfs(cur) 确定第 cur 个元素的状态：

• 选：把 nums[cur] 加入路径，递归 dfs(cur+1)，返回后撤销选择；
• 不选：直接递归 dfs(cur+1)。

当 cur == n 时，说明所有位置的状态都已确定，把当前路径的副本加入答案。

递归过程正好形成一棵完全二叉树，叶子节点共 $2^n$ 个，每个叶子对应一个子集。

代码

class Solution:
    def subsets(self, nums: list[int]) -> list[list[int]]:
        if len(nums) == 0:
            return [[]]
        after = self.subsets(nums[1:])
        ans = []
        for subset in after:
            ans.append(subset)
            ans.append(subset + [nums[0]])
        return ans

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

        def dfs(cur: int) -> None:
            if cur == n:
                ans.append(path[:])
                return
            # 选当前元素
            path.append(nums[cur])
            dfs(cur + 1)
            path.pop()
            # 不选当前元素
            dfs(cur + 1)

        dfs(0)
        return ans

复杂度分析

• 时间复杂度：$O(n \times 2^n)$，共 $2^n$ 个叶子节点，每个节点复制路径需要 $O(n)$。
• 空间复杂度：$O(n)$，递归栈深度为 $n$，路径数组长度为 $n$。

方法三：回溯（按起点枚举）

思路及解法

换一种回溯视角：在搜索树中，每个节点本身就是一个子集，因此每进入一层，先记录当前路径，然后从 start 位置开始逐个选择元素。

• dfs(start)：先把当前路径加入答案，然后从 start 开始，依次尝试选择 nums[i]；
• 每选一个就递归 dfs(i + 1)，返回后撤销。

start 参数保证每个元素只会被「往后选」，不会重复，也不会遗漏。

代码

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        n = len(nums)
        def fun(start, l):
            res.append(l)
            for i in range(start, n):
                fun(i+1, [nums[i]] + l)
        fun(0, [])
        return res

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

        def dfs(start: int) -> None:
            ans.append(path[:])   # 每个节点都是一个子集
            for i in range(start, n):
                path.append(nums[i])
                dfs(i + 1)
                path.pop()

        dfs(0)
        return ans

复杂度分析

• 时间复杂度：$O(n \times 2^n)$。
• 空间复杂度：$O(n)$。