78. 子集

题目链接：78. 子集

题目描述

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

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

核心思考：回溯法（选择与不选择）

本题是经典的状态空间搜索问题。对于数组中的每一个元素，我们都面临两种选择：将其纳入当前子集，或者不将其纳入当前子集。这种逻辑可以完美地通过深度优先搜索（DFS）即回溯法来实现。

1. 递归决策树：设当前递归深度为 i，代表我们正在决定是否要选取 nums[i]。
2. 两条分支：
   • 分支一（不选）：直接递归进入下一层 dfs(i + 1)。
   • 分支二（选）：将 nums[i] 加入当前路径 path，然后递归进入下一层 dfs(i + 1)，完成后执行回溯操作 path.pop()。
3. 终止条件：当 i 到达数组长度 n 时，说明所有元素都已做过决策。此时将 path 的一个拷贝（切片 path[:]）存入结果集 ans。

通过这种“选或不选”的二叉树路径搜索，我们可以不遗漏且不重复地遍历出所有共 $2^N$ 种可能。

解题思路 (Python)

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

        def dfs(i):
            # 终止条件：所有元素都已决策完毕
            if i == n:
                ans.append(path[:])
                return
            
            # 决策 1：不选当前数字，直接向后走
            dfs(i + 1)

            # 决策 2：选择当前数字
            path.append(nums[i])
            dfs(i + 1)
            # 回溯：重置状态
            path.pop()
        
        dfs(0)
        return ans

复杂度分析

• 时间复杂度：$O(N \times 2^N)$，其中 $N$ 是数组的长度。总共有 $2^N$ 个子集，且每个子集的拷贝操作消耗 $O(N)$。
• 空间复杂度：$O(N)$。递归栈的最大深度为 $N$，且辅助路径数组 path 的大小最大也为 $N$。