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）。
