Bitmasking and Subset Enumeration

Bitmasking & Subset Enumeration

Every one of the earlier pages treated an integer as a number. This page flips the lens: treat an integer as a set. If you have at most ~20 elements, the bits of a single int can encode which of them you have chosen — bit i is 1 exactly when element i is in the set. That one idea turns “loop over all subsets” into “count from 0 to 2n − 1,” and it is the machinery underneath the Subsets problem, Maximum-XOR, and the whole family of bitmask DP problems (travelling salesman, assignment, Hamiltonian paths). Get this page solid and those problems stop being magic.

An int is a set

Give each element an index 0..n−1. A subset is then an n-bit number (a mask): element i is present iff bit i is set. With three elements {a, b, c} at indices 0, 1, 2:

Set operations become bit operations, and this dictionary is worth memorizing because it is why bitmask DP is fast — a whole set fits in one register and unions/intersections are single instructions:

• Union A ∪ B → a | b
• Intersection A ∩ B → a & b
• Membership “is i in the set?” → (mask >> i) & 1
• Add element i → mask | (1 << i)
• Remove element i → mask & ~(1 << i)
• Size |A| → popcount(mask) (Integer.bitCount / bits.OnesCount)
• Complement (within n elements) → mask ^ ((1 << n) − 1)

Enumerating all 2ⁿ subsets — just count

Because a subset is an n-bit number, and the n-bit numbers are exactly 0, 1, 2, …, 2n−1, iterating every integer in that range visits every subset exactly once — no recursion, no bookkeeping. For each mask, read off which bits are set to recover the subset. The traced table above is that loop for n = 3: the decimal column runs 0..7 and each row is one subset.

Why exactly once and no duplicates? A subset corresponds to one and only one mask (a set of chosen indices maps bijectively to a bit pattern), and the loop hits each integer in [0, 2n) a single time. Bijection + one visit each = every subset produced exactly once.

Java: enumerate every subset

import java.util.*;

public class BitmaskSubsets {
    // All 2^n subsets of items[0..n-1], read straight off the bits.
    static List<List<Integer>> allSubsets(int[] items) {
        int n = items.length;
        List<List<Integer>> out = new ArrayList<>();
        for (int mask = 0; mask < (1 << n); mask++) {   // 0 .. 2^n - 1
            List<Integer> subset = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {           // is element i chosen?
                    subset.add(items[i]);
                }
            }
            out.add(subset);
        }
        return out;
    }

    public static void main(String[] args) {
        System.out.println(allSubsets(new int[]{1, 2, 3}));
        // [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
    }
}

Go: enumerate every subset

package main

import "fmt"

// allSubsets returns all 2^n subsets of items, read straight off the bits.
func allSubsets(items []int) [][]int {
	n := len(items)
	var out [][]int
	for mask := 0; mask < (1 << n); mask++ { // 0 .. 2^n - 1
		var subset []int
		for i := 0; i < n; i++ {
			if mask&(1<<i) != 0 { // is element i chosen?
				subset = append(subset, items[i])
			}
		}
		out = append(out, subset)
	}
	return out
}

func main() {
	fmt.Println(allSubsets([]int{1, 2, 3}))
	// [[] [1] [2] [1 2] [3] [1 3] [2 3] [1 2 3]]
}

Iterating only the set bits (the elements you actually have)

The inner loop above walks all n positions even for a nearly-empty mask. When you want to touch only the chosen elements, use the lowest-set-bit trick from the tricks page: repeatedly read the lowest set bit and clear it. Integer.numberOfTrailingZeros (Go: bits.TrailingZeros) turns the isolated low bit into its index.

for (int m = mask; m != 0; m &= (m - 1)) {   // m & (m-1) clears the lowest set bit
    int i = Integer.numberOfTrailingZeros(m); // index of that lowest set bit
    // ... use element i ...
}

This runs popcount(mask) times, not n times — the same Kernighan idea that made popcount data-dependent.

Submask enumeration — every subset of a chosen set

A subtler need: given a fixed mask, walk every submask of it — every set whose chosen bits are a subset of mask’s bits (formally, every s with s & mask == s). This is the core loop of bitmask DP where the state is “this group of items” and you must split it into a sub-group and its complement. The idiom is famously terse:

for (int s = mask; ; s = (s - 1) & mask) {
    process(s);          // s ranges over every submask, largest first
    if (s == 0) break;   // 0 (the empty submask) is the last one
}

Why s = (s - 1) & mask lands on the next submask down. Take the current submask s. Subtracting 1 flips s’s lowest set bit to 0 and turns every bit below it into 1 (a borrow, exactly as on the popcount page). Those newly-1 low bits may include positions that are not in mask — garbage we must not keep — so we & mask to snap back onto mask’s bits. The result is provably the largest submask strictly smaller than s: it clears one of s’s bits and refills with the highest-value mask-bits available below it. Because each step strictly decreases s yet stays a submask, the loop marches through all submasks in decreasing order and terminates at 0.

Traced for mask = 1011 (bits 0, 1, 3 set; it has 23 = 8 submasks):

The visited set {11, 10, 9, 8, 3, 2, 1, 0} is exactly the eight subsets of {0, 1, 3} — note it correctly skips masks like 0100 (4) and 0101 (5) that use bit 2, which is not in 1011.

Java: enumerate submasks

public class Submasks {
    static void submasks(int mask) {
        for (int s = mask; ; s = (s - 1) & mask) {
            System.out.print(s + " ");
            if (s == 0) break;   // include the empty submask, then stop
        }
        System.out.println();
    }

    public static void main(String[] args) {
        submasks(0b1011);   // 11 10 9 8 3 2 1 0
    }
}

Go: enumerate submasks

package main

import "fmt"

func submasks(mask int) {
	for s := mask; ; s = (s - 1) & mask {
		fmt.Print(s, " ")
		if s == 0 { // include the empty submask, then stop
			break
		}
	}
	fmt.Println()
}

func main() {
	submasks(0b1011) // 11 10 9 8 3 2 1 0
}

The 3ⁿ that surprises people

If you nest the submask loop inside a loop over all masks — the standard shape of subset-sum DP — the total work is not 2n × 2n. It is 3n, and the proof is a one-liner once you see it. Sum over every mask of its submask count. Look at one bit position across the (mask, submask) pair: it is in exactly one of three states — not in mask; in mask and in the submask; or in mask but not in the submask. Three independent choices per bit, n bits → 3n total (mask, submask) pairs. That is why “iterate all subsets, and for each all its subsets” is Θ(3n), not Θ(4n) — a fact interviewers love to probe.

The bridge to bitmask DP

Everything above is scaffolding for one pattern: let the DP state be a set, encoded as a mask. When n ≤ ~20, there are only 2n possible states, which is tractable, so a problem that is exponential in the naive framing (“try all orderings/assignments”) becomes a table indexed by mask. Two canonical shapes:

• Assignment / set-cover: dp[mask] = best cost to cover / assign the elements in mask. Fill masks in increasing order; each transition adds one element (mask | (1 << i)). Complexity O(2n · n).
• Travelling salesman / Hamiltonian path: dp[mask][i] = cheapest route visiting exactly the cities in mask and ending at i. Complexity O(2n · n2) — the reason TSP is “solvable” for n up to ~18–20 but not 100.

The neutral recurrence for the assignment shape (pseudocode — the mask arithmetic is exactly what this page taught):

dp[0] = 0
for mask in 1 .. (1<<n)-1:
    i = index of the next element to place   // e.g. popcount(mask)-1, or lowest unset bit
    dp[mask] = min over j in mask of
                   dp[mask without j] + cost(place element -> slot for j)

When bitmask enumeration is the right tool — and when it is not

• Use it when n is small. 220 ≈ 106 and 222 ≈ 4 × 106 are fine; a per-mask × n factor pushes the practical ceiling to about n ≤ 20–22. Beyond ~25 the 2n term alone is hundreds of millions and it stops being viable.
• Use it when you need a stable id per subset — the mask is an integer key, perfect for memoization, DP tables, or deduping subsets in a hash set. Backtracking gives you the subset but not a cheap canonical id.
• Do not use it when n is large. 2n is exponential; no bit trick rescues n = 40. If the structure allows, switch to meet-in-the-middle (split into two halves of n/2, enumerate 2n/2 each, combine) — that stretches the ceiling to n ≈ 40. For truly large n you need a polynomial algorithm (greedy / flow / DP-not-over-subsets) instead.
• Do not use it when you can prune. Straight enumeration always produces all 2n masks. If the problem has constraints that let you abandon most branches early (“subsets summing to exactly T”), backtracking with pruning can explore far fewer than 2n nodes — the subject of the Subsets problem page.

Traps

• 1 << n overflows past n = 30 in a 32-bit int. For n ≥ 31 use 1L << n in Java / a wider type; but at that size 2n is infeasible anyway, which is the real signal.
• Shift amount must be less than the type width. 1 << 32 is undefined-ish in Java (the shift count is taken mod 32, so it yields 1, not 0) — a silent, vicious bug. Keep n strictly within range.
• Membership test parenthesization — a Java trap, not a Go one. In Java, & binds looser than !=, so mask & (1 << i) != 0 parses as mask & ((1<<i) != 0) — which does not even compile against an int. Always write (mask & (1 << i)) != 0. In Go the precedence is the reverse (& is a multiplicative-level operator, tighter than !=), so the unparenthesized form actually compiles and is correct — but parenthesize anyway so the intent is portable and unmistakable.

Takeaways

• An int is a set of up to ~20–30 elements; bit i means “element i is in.” Union/intersection/membership are single bit ops.
• All 2n subsets = the integers 0..2n−1; the bijection guarantees each subset once, no recursion needed.
• s = (s-1) & mask walks every submask in decreasing order — a borrow that clears one bit, snapped back onto mask; nesting it over all masks is Θ(3n).
• This is the foundation of bitmask DP: state = mask, tractable only while n stays small.

First-principles treatment of set/int duality, the submask-enumeration invariant, the 3n counting argument, and the bitmask-DP bridge; both samples were compiled and run to confirm the stated output.