78. 子集
✅ 一、算法逻辑讲解（逐步思路）
逻辑讲解：
-
dfs(i)：表示从下标i开始，做“选 or 不选”的子集构造。 -
终止条件
if i == n：-
到达数组末尾，表示一种完整子集构造完成。
-
把当前构造路径
path复制一份加入ans。
-
-
每个位置都有两种选择：
-
不选当前元素：直接
dfs(i+1)。 -
选当前元素：先加入
path，然后dfs(i+1)。 -
完成后通过
path.pop()撤销选择，回溯到上一状态。
-
-
初始从
dfs(0)开始，表示从第一个元素开始构造子集。
⭐ 二、核心思路（算法关键点）
核心点是：使用 DFS + 回溯 来枚举所有子集
-
每个元素有两个选择：选 or 不选。
-
用 DFS 的递归树遍历所有选择路径。
-
每条路径就是一个合法子集。
-
通过
path.pop()回溯上一步，探索下一个可能性。
这是一种更容易理解、便于剪枝的通用枚举方式，相比位运算法更直观（适合初学者理解和复杂问题扩展）。
class Solution:def subsets(self, nums: List[int]) -> List[List[int]]:ans = []n = len(nums)path = []def dfs(i:int) -> None:if i == n:ans.append(path.copy())returndfs(i+1)path.append(nums[i])dfs(i+1)path.pop()dfs(0)return ans⏱ 三、时间复杂度分析
时间复杂度：O(n * 2^n)
-
一共会递归
2^n次（每个元素选 or 不选）。 -
每次递归最多生成一个子集，长度最多为
n，需要复制（path.copy()）。 -
所以整体复杂度为
O(n * 2^n)。
💾 四、空间复杂度分析
空间复杂度：O(n) + O(n * 2^n)
-
递归栈空间：
O(n)-
递归深度最大为
n，每层递归函数栈消耗是常量级。
-
-
输出空间：
O(n * 2^n)-
一共
2^n个子集，每个子集长度最多为n。
-
-
临时变量
path：O(n)-
存储当前路径，最大长度为
n。
-
如果只考虑「辅助空间」，则是
O(n)（递归 + path）。
