Subset EnumerationEnumerating subsets with bits

01Why it exists

Reach for it when you see:n ≤ 20, each element either chosen or not, a set stored as a single integer, trying every combination, union and intersection of sets, listing all subsets of a given set, 3ⁿ, n around 40 (meet in the middle), the state of a bitmask DP.

02The core idea

Subsets and binary line up perfectly. With n elements, each one is either in or out — exactly the 1 or 0 of a single bit. Agree that bit i stands for element i, and an n-bit integer mask is a subset. Every subset has one and only one binary spelling, so the 2ⁿ integers from 0 to 2ⁿ − 1 are in one-to-one correspondence with the 2ⁿ subsets, and a single loop counting up from 0 hits each exactly once. Set operations turn into bit operations too: mask >> i & 1 asks whether element i is in, a | b is union, a & b is intersection, (a & b) == a says a is a subset of b, and the number of 1s (the popcount) is the size of the subset.

The second trick is enumerating only the submasks of a given mask: start at sub = mask and repeatedly set sub = (sub - 1) & mask until you reach 0. Here is why it works. Pull out the k positions where mask has a 1; the value of sub at those positions can be read as a k-bit number. Subtracting 1 turns sub's lowest set bit into a 0 and every bit below it into a 1; ANDing back with mask then clears everything outside mask, and what is left is exactly "that k-bit number minus 1". So in those extracted coordinates sub counts down from 2ᵏ − 1 all the way to 0, passing through each submask exactly once and skipping every integer in between that is not a submask. You have to finish processing the empty set before you stop, because (0 - 1) & mask takes you back to mask.

The enumeration itself is 2ⁿ integers with O(1) to step to the next, and the only extra space is one integer, so it is O(2ⁿ) time and O(1) space. But you usually have to do something with each mask, and checking bit by bit which elements are in costs O(n), making the whole thing O(2ⁿ·n). If the quantity you want has a recurrence — subset sums, say — you can lean on the fact that mask's own value is already computed before bit i is added, which makes each subset O(1) and the total O(2ⁿ) time, at the cost of a table of size 2ⁿ. And if you enumerate the submasks of every mask, each element is in exactly one of three states — outside mask, in mask but not in sub, or in both — so the total is 3ⁿ, not 4ⁿ. The practical ceilings: 2ⁿ works up to n ≤ 20 (a million) and 3ⁿ up to n ≤ 15 (fourteen million); at n around 40, switch to meet in the middle, with 2²⁰ per half and a merge at the end.

Three traps come up again and again. In C++ == binds tighter than &, so mask & 1 << i == 0 actually means mask & ((1 << i) == 0) and the condition is never true — parenthesise bit operations, always. 1 << n overflows once n ≥ 31, so write 1LL << n. And binary reads right to left, so it is the rightmost bit that is element 0. Compared with the backtracking in Subsets, both walk all 2ⁿ subsets; backtracking can prune partway through and bit enumeration cannot, but bit enumeration has no recursion, a small constant factor, and a subset that is already an integer, so it doubles as an array index or a hash table key. That is exactly the door into bitmask DP: dp[mask] holds the best value once the elements in mask are handled, and submask enumeration is the transition that splits mask into two pieces.

03The algorithm

1. 1Check the size. Enumerating every subset needs n ≤ 20 or so; also listing the submasks of every subset (3ⁿ) needs n ≤ 15 or so; at n around 40, split into two halves and enumerate each. Number the elements 0 to n − 1, with bit i standing for element i.
2. 2The outer loop is for mask in range(1 << n), and each integer is one subset. In C++, switch to 1LL << n when n can reach 31 or more.
3. 3Inside, use mask >> i & 1 to pull out which elements are chosen and accumulate whatever you need (a sum, an OR of skills, a conflict check). The size of the subset is the popcount of mask, so if you only want subsets of size exactly k, use it to filter the rest out first.
4. 4If the quantity you need can be built from "the subset with one element fewer", fill a table of size 2ⁿ instead: for each i and each mask < 1 << i, set f[mask | 1 << i] = f[mask] + a[i], which drops the inner O(n).
5. 5For the submasks of one mask: start at sub = mask, and after processing sub stop if sub == 0, otherwise sub = (sub - 1) & mask. When you do not want the empty set, the loop condition can just be sub > 0.

04Interactive demo

The elements are A, B, C, D, and bit i stands for element i, so A is bit 0 on the far right. In the first half, mask counts from 0 to 15: on the left are the four bits of the current mask, with blue bits set to 1 and the chosen elements in green underneath; in the 16 cells on the right, blue is the current mask and green marks the ones already listed. The second half lists only the submasks of mask = 1011₂ (A, B, D), so the C bit is drawn dashed and stays 0, and cells that are not submasks turn grey. Watch sub jump straight from 1000₂ to 0011₂ — the four integers in between all contain C and are skipped by a single AND — and stop after all eight submasks.

05Code

Four functions. The core mask loop lists every subset; using it to find the smallest fully skilled team shows OR as union and popcount as headcount; the O(2ⁿ) recurrence for subset sums is what meet in the middle runs once on each half; and last comes submask enumeration, with a check that listing the submasks of every mask really does take 3ⁿ steps. The C++ version uses only the standard std::bitset to count 1s and print binary.

# Bit i set means element i is chosen: every integer from 0 to 2ⁿ−1 is exactly one subset
def subsets(items):
    n = len(items)
    out = []
    for mask in range(1 << n):                   # 2ⁿ masks
        out.append([items[i] for i in range(n) if mask >> i & 1])
    return out


# Application: skills[i] is person i's skill set as bits. Smallest team whose skills cover 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]                # union is OR
        if (have & need) == need and (best == -1 or mask.bit_count() < best.bit_count()):
            best = mask                          # bit_count() is the size of the team
    if best == -1:
        return None                              # even everybody together falls short
    return [i for i in range(n) if best >> i & 1]


# Sum of every subset, O(2ⁿ): before bit i is added to mask, mask's own sum is already known
def subset_sums(nums):
    sums = [0] * (1 << len(nums))
    for i, x in enumerate(nums):
        for mask in range(1 << i):               # subsets of the first i elements only
            sums[mask | 1 << i] = sums[mask] + x
    return sums


# Every submask of mask, largest first, including mask itself and 0
def submasks(mask):
    sub = mask
    while True:
        yield sub
        if sub == 0:                             # stop after 0, else (0 - 1) & mask jumps back to mask
            break
        sub = (sub - 1) & mask                   # subtract 1, AND back with mask, next submask


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

    # bit 0 frontend, bit 1 backend, bit 2 database, 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                                        # list the submasks of every mask: 3ⁿ in total
    print(sum(1 for mask in range(1 << n) for _ in submasks(mask)), 3 ** n)   # 243 243

06Practice

• LeetCode 78Subsets (use a mask loop instead of recursion)Medium
• LeetCode 2212Maximum Points in an Archery Competition (enumerate which sections to win)Medium
• LeetCode 2397Maximum Rows Covered by Columns (store each row as a mask)Medium
• LeetCode 2002Maximum Product of the Length of Two Palindromic Subsequences (two disjoint masks)Medium
• LeetCode 1178Number of Valid Words for Each Puzzle (submask enumeration)Hard
• LeetCode 1755Closest Subsequence Sum (meet in the middle)Hard