78. Subsets

──────────────────────────────────────────────────────────────────────

78. Subsets

給一個沒有重複元素的陣列，回傳所有子集（冪集合）。

思路

子集和排列的差別在於順序不重要：[1,2] 和 [2,1] 是同一個子集，只能算一次。

要避免重複，作法是規定「只能往後選」—— 每一層都從上一次選的索引之後開始挑，這樣任何一個子集都只會用「索引遞增」的那一種順序被產生出來，天然不重複。這就是 start 參數的用途。

	每一層可以選什麼	用什麼控制
子集 / 組合（本題）	只能選索引比上一個大的	`start` 參數
46. 排列	全部元素，只要還沒用過	`visited` 集合

第二個關鍵是什麼時候收集答案：

每進入一個節點就收集一次，不是只在葉節點收集。

因為回溯樹上的每一個節點都是一個合法的子集 —— 根節點是空集合、第一層是單元素子集⋯⋯所以 res.append(list(curr)) 要放在函式的最上面，而且沒有終止條件（for 迴圈跑完自然就返回了）。

這一點是子集題和其他回溯題最大的不同。46 要等 len(curr) == len(nums)、39 要等 target == 0，只有子集題是「隨走隨收」。

解題方向

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:

        res = []
        n = len(nums)

        def backtrack(curr, start):
            res.append(list(curr))
            
            for i in range(start, n):
                curr.append(nums[i])
                backtrack(curr, i + 1)
                curr.pop()
        

        backtrack([], 0)
        
        return res

三個要點：

res.append(list(curr)) 在最前面 —— 每個節點都是答案，理由見上面
list(curr) 的複製不能省 —— curr 是同一個 list 一路被修改，直接放進去的話最後全部會變成空的
遞迴傳的是 i + 1 不是 start + 1 —— 要從「剛選的這個」的下一個開始，傳 start + 1 會讓同一層的不同分支互相干擾

for i in range(start, n) 配 backtrack(curr, i + 1) 是組合型回溯的固定骨架，見 Backtracking 模板。

補充

另一種思路：把子集看成二進位。 n 個元素的每個子集都對應一個 n 位元的 0/1 遮罩（第 i 位是 1 代表選了 nums[i]），所以枚舉 0 到 2^n - 1 就枚舉完所有子集了：

        res = []
        for mask in range(1 << len(nums)):
            res.append([nums[i] for i in range(len(nums)) if mask & (1 << i)])
        return res

複雜度一樣，但完全不用遞迴。這個「子集 ↔ 位元遮罩」的對應在狀態壓縮 DP 裡很常用，值得知道。

有重複元素的版本是 90. Subsets II：先排序，然後在同一層跳過重複值（if i > start and nums[i] == nums[i-1]: continue）。注意條件是 i > start 不是 i > 0 —— 只跳過同一層的重複，不影響往下遞迴時再次選到相同的值。

同一個 start 骨架的其他題：77. Combinations（固定長度）、39. Combination Sum（可以重複選同一個，所以傳 i 而不是 i + 1）、131. Palindrome Partitioning。

複雜度

時間 $O (n \times 2^{n})$ — 有 $2^{n}$ 個子集，每個平均要花 $O (n)$ 複製進結果
空間 $O (n)$ — 遞迴深度最多 n，curr 也是 $O (n)$ （不含輸出）

其中 n 是元素個數。和 46. Permutations 一樣，輸出本身就是這個量級，所以沒有更快的解法 —— 被問到「能不能優化」時這就是答案。