演算法圖鑑
Recursion & Backtracking · 01 / 05

Subsets子集

每個元素選或不選，2ⁿ 種。

用在：功能開關組合測試、冪集列舉

時間複雜度O(2ⁿ·n)
空間複雜度O(n)
難度進階
前置知識Recursion

01為什麼需要它

功能開關的組合測試

系統有 5 個功能開關（深色模式、新結帳流程、實驗性搜尋……），QA 要確認任何一種開關組合都不會互相打架。每個開關可開可關，總共有幾種情況、要怎麼一個不漏地列出來？

為什麼用它每個開關「開或關」就是每個元素「選或不選」。逐一決定每個開關，決定完就是一種組合，回頭改上一個決定再往下走，2⁵ = 32 種組合一個不漏、一個不重。

選幾樣配菜的所有套餐

便當店有 4 種配菜可以任選，菜單要列出所有可能的套餐（含不選任何配菜）。老闆手寫漏了兩種，客人來問才發現。

為什麼用它手寫會漏是因為沒有系統性的順序。子集列舉給的就是一個順序：第一樣選不選、第二樣選不選……走到底就是一份套餐，2⁴ = 16 種保證完整。

從一堆數字裡找出總和等於目標的組合

報帳時只知道總金額是 1,250 元，發票有 8 張，要找出哪幾張加起來剛好是這個數。

為什麼用它8 張發票的每個子集都算一次總和就好，2⁸ = 256 種完全跑得動。子集列舉是這類「試遍所有組合」問題的地基，之後的組合、剪枝都從它長出來。

看到這些關鍵字就想到它：所有組合、任選幾個、每個可以要或不要、冪集、開關的每種狀態、n 很小（≤ 20）而要列出全部。

02核心概念

子集問題是回溯的第一課，因為它的決策樹最單純：對第 i 個元素只有兩個選擇，選或不選。從 nums[0] 開始，每往下一層決定一個元素，走到第 n 層時每個元素都有了決定，那時的路徑就是一個子集。n 個元素每個兩種選擇，葉節點共 2ⁿ 個，每個子集恰好對應一個葉，所以不重不漏。

回溯的骨架就是三步：做選擇（把 nums[i] 放進 path）、遞迴（處理 i+1）、撤銷選擇（把 nums[i] 從 path 拿掉）。撤銷是關鍵，因為 path 是所有遞迴呼叫共用的同一個陣列，回到上一層時它必須長得和離開前一模一樣，下一個分支才能在正確的狀態上繼續。收集答案時要 path[:] 複製一份，否則之後的 pop 會把已經收進答案的子集也改掉。

複雜度來自兩個因子：葉節點有 2ⁿ 個，每個子集複製要 O(n)，所以 O(2ⁿ·n)。這無法再壓，因為每個元素出現在一半的子集裡，光是把答案寫出來就有 n·2ⁿ⁻¹ 個數字。空間只有遞迴深度和 path 的 O(n)（不算輸出）。這也說明為什麼回溯只適合 n 小的問題：n = 20 約一百萬個子集，n = 40 就超過一兆。

另一種常見寫法是每層決定「下一個放誰」，用 start 只往右挑，樹上每個節點（不只是葉）都是一個子集。這個寫法和組合問題長得一樣，也比較容易處理重複元素：先排序，同一層裡若 j > start 且 nums[j] == nums[j-1] 就跳過，因為「這個位置放這個值」的分支剛才已經走過一遍了。j > start 不能省：少了它，連 [2, 2] 這種「往下一層再放一個相同的值」也會被跳過。

03演算法步驟

  1. 1準備 ans（答案）與 path（目前路徑），寫 dfs(i) 表示「正在決定第 i 個元素」。
  2. 2終止條件：i == len(nums)，所有元素都決定了，把 path 複製一份放進 ans。
  3. 3做選擇：path.append(nums[i])，遞迴 dfs(i + 1)。
  4. 4撤銷選擇：path.pop()，讓 path 回到進入這一層時的樣子。
  5. 5走另一條路：不放 nums[i]，直接 dfs(i + 1)。兩條路都走完，這一層結束，回到上一層。

04互動示範

[1, 2, 3] 的決策樹。樹上每個節點寫著目前的路徑，左邊分支是「選」、右邊是「不選」。留意每次撤銷後路徑會退回剛進入那一層時的樣子，8 個葉節點正好是 8 個子集。

開始nums = [1, 2, 3] · 左邊：選，右邊：不選
∅1選 112選 2123選 312不選 31不選 213選 31不選 3∅不選 12選 223選 32不選 3∅不選 23選 3∅不選 3
nums（i = 0）
123
目前路徑
空
已收集的子集（0/8）
還沒有
步驟 0/30對 3 個元素逐一決定「選」或「不選」。每往下一層決定一個元素，走到底就得到一個子集。

05程式碼

三個版本：選或不選的標準寫法、用 start 的寫法（每個節點都是子集），以及處理重複元素的版本。

# 子集（LeetCode 78）：每個元素「選」或「不選」
def subsets(nums):
    ans = []
    path = []

    def dfs(i):
        if i == len(nums):            # 每個元素都決定完了
            ans.append(path[:])       # 複製一份，path 之後還會變
            return
        path.append(nums[i])          # 做選擇：選 nums[i]
        dfs(i + 1)
        path.pop()                    # 撤銷選擇
        dfs(i + 1)                    # 另一條路：不選 nums[i]

    dfs(0)
    return ans


# 另一種寫法：每層決定「下一個放誰」，每個節點都是一個子集
# 用 start 只往右挑，所以不會同時產生 [1, 2] 和 [2, 1]
def subsets_start(nums):
    ans = []
    path = []

    def dfs(start):
        ans.append(path[:])           # 進到節點就收集
        for j in range(start, len(nums)):
            path.append(nums[j])
            dfs(j + 1)
            path.pop()

    dfs(0)
    return ans


# 含重複元素的子集（LeetCode 90）：先排序，同一層跳過相同的值
def subsets_with_dup(nums):
    nums = sorted(nums)               # 排序出新串列，不改動呼叫者的輸入
    ans = []
    path = []

    def dfs(start):
        ans.append(path[:])
        for j in range(start, len(nums)):
            if j > start and nums[j] == nums[j - 1]:   # 同一層已經試過這個值
                continue
            path.append(nums[j])
            dfs(j + 1)
            path.pop()

    dfs(0)
    return ans


if __name__ == "__main__":
    print(subsets([1, 2, 3]))
    # [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]
    print(subsets_start([1, 2, 3]))
    # [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
    print(subsets_with_dup([1, 2, 2]))
    # [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]

06練習題

  • LeetCode 78SubsetsMedium
  • LeetCode 90Subsets II（排序後同層跳過重複）Medium
  • LeetCode 784Letter Case Permutation（每個字母選大寫或小寫）Medium
  • LeetCode 1863Sum of All Subset XOR TotalsEasy
  • LeetCode 2044Count Number of Maximum Bitwise-OR SubsetsMedium
  • LeetCode 698Partition to K Equal Sum Subsets（每個數字決定放進哪個子集，加剪枝）Medium
上一篇—下一篇Permutations