題目描述:給定一個不含重複元素的整數陣列 nums,回傳其所有可能的子集(冪集)。答案集合中不得有重複的子集,回傳順序不限。
解題思路:使用回溯法(Backtracking)系統性地枚舉所有子集。核心思路是:在每一層遞迴中,從 start 索引開始依序考慮每個元素是否加入當前子集。每次進入一個元素,先將該元素加入暫存路徑 path,並立即將 path 的快照加入答案(因為每個中間狀態都是合法子集),然後以 i+1 為新的起始點繼續遞迴,探索包含更多元素的子集;遞迴返回後將元素從 path 移除(回溯),換下一個元素繼續。這樣可以確保不重複、不遺漏地產生所有 2ⁿ 個子集。
時間複雜度:O(n · 2ⁿ) — 共有 2ⁿ 個子集,每個子集平均長度為 n/2,複製至答案的總成本為 O(n · 2ⁿ)。
空間複雜度:O(n) — 遞迴呼叫堆疊深度最多為 n,暫存路徑 path 最多儲存 n 個元素(不計輸出空間)。
1. Define backtrack(start, path):
a. Append a copy of path to result
b. For i from start to len(nums)-1:
i. Push nums[i] onto path
ii. Recurse: backtrack(i+1, path)
iii.Pop last element from path (backtrack)
2. Call backtrack(0, [])
3. Return result迭代法 O(n · 2ⁿ):從空集合開始,對每個新元素,將它加入所有已存在的子集,形成新的子集並合併至答案。實作直觀但需複製大量子集。
位元遮罩法 O(n · 2ⁿ):用 0 到 2ⁿ-1 的整數表示每個子集,第 k 個位元為 1 表示選取 nums[k]。不需遞迴,程式碼簡潔,但可讀性略低於回溯法。