Subset Enumeration位元列舉子集

01為什麼需要它

看到這些關鍵字就想到它：n ≤ 20、每個元素選或不選、把集合存成一個整數、所有組合都試一遍、集合的聯集與交集、列出某個集合的所有子集合、3ⁿ、n 在 40 左右（折半列舉）、Bitmask DP 的狀態。

02核心概念

子集和二進位天生對得上：n 個元素，每個只有選或不選兩種狀態，剛好是一個位元的 1 或 0。約定第 i 位對應第 i 個元素，一個 n 位元的整數 mask 就代表一個子集。每個子集的二進位寫法唯一，所以 0 到 2ⁿ − 1 這 2ⁿ 個整數和 2ⁿ 個子集一一對應，一個迴圈從 0 數上去就不重不漏。集合運算也全變成位元運算：mask >> i & 1 問第 i 個有沒有選、a | b 是聯集、a & b 是交集、(a & b) == a 表示 a 是 b 的子集、1 的個數（popcount）就是子集大小。

第二個技巧是只列舉某個 mask 的子集合：從 sub = mask 開始，每次 sub = (sub - 1) & mask，到 0 為止。為什麼正確：把 mask 裡是 1 的那 k 個位置抽出來，sub 在這些位置上的值可以看成一個 k 位元的數。減 1 會把 sub 最低位的 1 變成 0、它下面的位全變成 1；再 AND 回 mask，mask 以外的位被清掉，留下的恰好是「那個 k 位元的數減 1」。所以 sub 在抽出來的座標裡從 2ᵏ − 1 一路倒數到 0，每個子集合正好經過一次，中間不是子集合的整數全被跳過。空集合要處理完才停，因為 (0 - 1) & mask 又會回到 mask。

列舉本身是 2ⁿ 個整數、每個 O(1) 前進到下一個，額外空間只有一個整數，這就是 O(2ⁿ) 時間、O(1) 空間。但每個 mask 通常還要做事：逐位檢查選了誰要 O(n)，整體變成 O(2ⁿ·n)。如果要的量可以遞推（例如子集總和），利用「mask 加上第 i 位之前，mask 本身已經算好」，每個子集 O(1)，總共 O(2ⁿ) 時間，代價是 O(2ⁿ) 的表。若對每一個 mask 都列舉它的子集合，每個元素只有「不在 mask」「在 mask 但不在 sub」「兩邊都在」三種狀態，總次數是 3ⁿ 而不是 4ⁿ。實用上限大約是：2ⁿ 做到 n ≤ 20（一百萬）、3ⁿ 做到 n ≤ 15（一千四百萬）；n 在 40 左右就用折半列舉，兩半各 2²⁰ 個再合併。

常見的坑：C++ 裡 == 比 & 先算，mask & 1 << i == 0 其實是 mask & ((1 << i) == 0)，條件永遠不成立，位元運算一律加括號；1 << n 在 n ≥ 31 時溢位，要寫 1LL << n；二進位從右往左讀，最右邊才是第 0 個元素。和 Subsets 的回溯相比，兩者都走過 2ⁿ 個子集，回溯能在半路剪枝，位元列舉不能，但它沒有遞迴、常數小，而且子集本身就是一個整數，可以直接當陣列索引或雜湊表的 key。這正是 Bitmask DP 的入口：dp[mask] 記錄「mask 這些元素處理完」的最佳值，子集合列舉對應「把 mask 拆成兩塊」的轉移。

03演算法步驟

1. 1確認規模：列舉所有子集要 n ≤ 20 左右；還要列每個子集的子集合（3ⁿ）要 n ≤ 15 左右；n 在 40 左右就拆成兩半各自列舉。把元素編號 0 到 n − 1，第 i 位對應第 i 個元素。
2. 2外層迴圈 for mask in range(1 << n)，每個整數就是一個子集。C++ 裡 n 可能到 31 以上時改用 1LL << n。
3. 3內層用 mask >> i & 1 取出選了哪些元素，累積要算的量（總和、技能的 OR、有沒有衝突）。子集大小是 mask 的 popcount，只要大小恰好 k 的子集就先用它篩掉其他的。
4. 4要算的量若能由「少一個元素的子集」推出，就開一張大小 2ⁿ 的表遞推：對每個 i 與 mask < 1 << i，f[mask | 1 << i] = f[mask] + a[i]，省掉內層的 O(n)。
5. 5只要某個 mask 的子集合：sub = mask，處理完 sub 後若 sub == 0 就停，否則 sub = (sub - 1) & mask。不需要空集合時，迴圈條件直接寫 sub > 0。

04互動示範

元素是 A、B、C、D，第 i 位對應第 i 個元素，所以 A 是最右邊的 bit 0。前半段 mask 從 0 數到 15：左邊是目前 mask 的 4 個位元，藍色的位是 1，底下綠色的就是被選的元素；右邊 16 格裡藍色是目前的 mask，綠色是已經列過的。後半段只列 mask = 1011₂（A、B、D）的子 mask，C 那一位畫成虛線、永遠是 0，不是子 mask 的格子變灰。留意 sub 從 1000₂ 一步跳到 0011₂，中間四個含 C 的整數被 AND 一次跳過，8 個子 mask 走完就停。

05程式碼

四個函式：核心的 mask 迴圈列出所有子集；用它找人數最少、技能全包的小組，示範 OR 做聯集、popcount 算人數；子集總和的 O(2ⁿ) 遞推，折半列舉就是對兩半各跑一次它；最後是子集合列舉，並驗證對所有 mask 各列一次總共是 3ⁿ 次。C++ 只用標準的 std::bitset 數 1 的個數和印二進位。

# 第 i 位是 1 代表選了第 i 個元素：0 到 2ⁿ−1 每個整數恰好是一個子集
def subsets(items):
    n = len(items)
    out = []
    for mask in range(1 << n):                   # 2ⁿ 個 mask
        out.append([items[i] for i in range(n) if mask >> i & 1])
    return out


# 應用：skills[i] 是第 i 個人會的技能（位元集合），找人數最少、技能涵蓋 need 的小組
def smallest_team(skills, need):
    n = len(skills)
    best = -1
    for mask in range(1 << n):
        have = 0
        for i in range(n):
            if mask >> i & 1:
                have |= skills[i]                # 聯集就是 OR
        if (have & need) == need and (best == -1 or mask.bit_count() < best.bit_count()):
            best = mask                          # bit_count() 就是小組人數
    if best == -1:
        return None                              # 所有人加起來也湊不齊
    return [i for i in range(n) if best >> i & 1]


# 所有子集的總和，O(2ⁿ)：mask 加上第 i 位之前，mask 的總和已經算好
def subset_sums(nums):
    sums = [0] * (1 << len(nums))
    for i, x in enumerate(nums):
        for mask in range(1 << i):               # 只用到前 i 個元素的子集
            sums[mask | 1 << i] = sums[mask] + x
    return sums


# mask 的所有子集合，由大到小，包含 mask 本身和 0
def submasks(mask):
    sub = mask
    while True:
        yield sub
        if sub == 0:                             # 0 處理完才停，否則 (0 - 1) & mask 又回到 mask
            break
        sub = (sub - 1) & mask                   # 減 1 再 AND 回 mask，跳到下一個子集合


if __name__ == "__main__":
    print(subsets(["A", "B", "C"]))
    # [[], ['A'], ['B'], ['A', 'B'], ['C'], ['A', 'C'], ['B', 'C'], ['A', 'B', 'C']]

    # bit 0 前端、bit 1 後端、bit 2 資料庫、bit 3 DevOps
    skills = [0b0011, 0b0100, 0b1100, 0b0001, 0b1010]
    print(smallest_team(skills, 0b1111))         # [0, 2]

    print(subset_sums([3, 5, 9]))                # [0, 3, 5, 8, 9, 12, 14, 17]
    print([format(s, "04b") for s in submasks(0b1011)])
    # ['1011', '1010', '1001', '1000', '0011', '0010', '0001', '0000']

    n = 5                                        # 對每個 mask 各列一次子集合，總共 3ⁿ 次
    print(sum(1 for mask in range(1 << n) for _ in submasks(mask)), 3 ** n)   # 243 243

06練習題

• LeetCode 78Subsets（改用 mask 迴圈，不用遞迴）Medium
• LeetCode 2212Maximum Points in an Archery Competition（列舉要贏哪幾區）Medium
• LeetCode 2397Maximum Rows Covered by Columns（每一列存成 mask）Medium
• LeetCode 2002Maximum Product of the Length of Two Palindromic Subsequences（兩個不相交的 mask）Medium
• LeetCode 1178Number of Valid Words for Each Puzzle（子集合列舉）Hard
• LeetCode 1755Closest Subsequence Sum（折半列舉）Hard