Bitmask DP, in depth: subsets as integers, the add-one, submask and sum-over-subsets transitions, a worked assignment table, partitions and the limits of n

Subsets as integers

Number the items 0 to n-1 and represent a subset as an integer whose bit j is 1 when item j is in the set. The empty set is 0 and the full set is (1 << n) - 1. Every set operation becomes one machine instruction, which is why the DP is fast enough to be practical. If two's complement and shifts are unfamiliar, Bit Manipulation Fundamentals covers them first.

The state is dp[mask], sometimes dp[mask][last] when position matters too. As in any dynamic program, define what a state means, where it comes from, and an order that computes predecessors first.

Three transition shapes

Nearly every bitmask DP uses one or more of three transition shapes. Recognising which one you need tells you the running time before you write code.

1. Add one element. From state S you move to S | 1 << j for each j not in S. There are n transitions per state: O(n · 2ⁿ). Assignment and sequencing problems are this shape. Because S | 1 << j > S, plain increasing integer order is a valid evaluation order.
2. Pick a whole submask. From S you choose any non-empty subset T of S as the next block, typically a group in a partition, and recurse on S \ T. Summed over all S, the number of (S, T) pairs is 3ⁿ, because each item is independently outside S, in S but not T, or in T. That is O(3ⁿ), much steeper than 2ⁿ.
3. Aggregate over all subsets. You need, for every S, a sum, minimum or count over all subsets of S. Doing this naively is again 3ⁿ; the sum-over-subsets transform (also called the zeta transform) does it in O(n · 2ⁿ) by adding one dimension at a time.

The diagram shows the first shape on three items; every arrow adds one bit.

Worked example: three workers, three jobs

Three workers, three jobs, and cost[i][j] is what worker i charges for job j:

Let workers choose in a fixed order. The state then only records which jobs are taken; their count says whose turn it is. Define dp[mask] as the cheapest total for giving the jobs in mask to workers 0 to popcount(mask) - 1. Then dp[0] = 0 and dp[mask | 1 << j] = min(dp[mask] + cost[popcount(mask)][j]) over the free jobs j.

The optimum is 9. Walking back: 111 was reached from 011 by giving job 2 to worker 2; 011 from 010 by giving job 0 to worker 1; 010 means worker 0 took job 1. Check: 2 + 6 + 1 = 9, and the six permutations give 9, 10, 14, 16, 20 and 21, so 9 is the minimum.

Implementation with reconstruction

The implementation stores, for every mask, the job whose addition produced its best value. Reconstruction walks backwards from the full mask, peeling off one job per worker.

def assign(cost):
    """cost[i][j] = cost of worker i doing job j. Returns (total, job_of_worker)."""
    n = len(cost)
    INF = float("inf")
    dp = [INF] * (1 << n)          # dp[mask]: cheapest way to give jobs in mask
    choice = [-1] * (1 << n)       #           to workers 0..popcount(mask)-1
    dp[0] = 0
    for mask in range(1 << n):     # increasing order: every predecessor is smaller
        if dp[mask] == INF:
            continue
        i = mask.bit_count()       # next worker to place (Python 3.10+)
        if i == n:
            continue
        for j in range(n):
            if not mask >> j & 1:
                nxt = mask | 1 << j
                cand = dp[mask] + cost[i][j]
                if cand < dp[nxt]:
                    dp[nxt], choice[nxt] = cand, j
    full = (1 << n) - 1
    job_of, mask = [0] * n, full
    for i in range(n - 1, -1, -1): # walk back: the last worker placed is n-1
        j = choice[mask]
        job_of[i] = j
        mask ^= 1 << j
    return dp[full], job_of

print(assign([[9, 2, 7], [6, 4, 3], [5, 8, 1]]))   # (9, [1, 0, 2])

Increasing integer order is valid because every transition sets a bit, so the source is numerically smaller than the target. Reconstruction uses the fact that worker popcount(mask) - 1 was the last one placed in mask, which is why the walk runs from worker n-1 down. Before trusting it, compare it with a brute force over itertools.permutations on a few hundred random matrices with n up to 7, checking both the value and that the reconstructed assignment is a permutation with that cost.

For plain assignment at large n, use the O(n³) Hungarian algorithm. The bitmask version earns its place when a price depends on which jobs are already taken, which dp[mask] handles by reading the mask.

Partitions and submask enumeration

The second shape solves partitions: split items into valid groups, minimising their number. The state is the set still to place; a transition removes one whole group. Enumerating every submask of a mask M uses the walk sub = (sub - 1) & M, which visits the submasks in decreasing order and reaches 0 last.

One trick halves the work and removes duplicates: the group that contains the lowest remaining item must exist, so always build that group first. Without it, the partition {A, B} would be found once as A then B and once as B then A.

def min_groups(weights, cap):
    """Fewest groups so that every group's total weight <= cap."""
    n = len(weights)
    total = [0] * (1 << n)
    for mask in range(1, 1 << n):
        low = mask & -mask                       # lowest set bit
        total[mask] = total[mask ^ low] + weights[low.bit_length() - 1]
    INF = float("inf")
    dp = [INF] * (1 << n)
    dp[0] = 0
    for mask in range(1, 1 << n):
        low = mask & -mask
        rest = mask ^ low
        sub = rest
        while True:                              # every submask of rest ...
            group = sub | low                    # ... plus the lowest element
            if total[group] <= cap and dp[mask ^ group] + 1 < dp[mask]:
                dp[mask] = dp[mask ^ group] + 1
            if sub == 0:
                break
            sub = (sub - 1) & rest
    return dp[(1 << n) - 1]

print(min_groups([4, 8, 1, 4, 2, 1], 10))        # 2

Here six packages weighing 4, 8, 1, 4, 2 and 1 must go into trucks holding at most 10. The total is 20, so two trucks is a lower bound, and {8, 2} with {4, 4, 1, 1} meets it; the DP returns 2. Note that total[mask] is itself a tiny DP, one addition per mask.

The price is 3ⁿ, which limits this shape to roughly n = 20. When the groups are interchangeable bins, the classic alternative state is dp[mask] = (bins used, fill of the current bin), which only adds one item at a time and runs in O(n · 2ⁿ).

Sum over subsets

The third shape answers questions like: for every set of ingredients S that a kitchen might stock, how many recipes can it cook? A recipe is cookable when its required set is a subset of S. Let a[s] count the recipes requiring exactly s; you want f[S] = sum of a[s] over all s ⊆ S, for all S at once.

The sum-over-subsets transform processes one bit at a time. After handling bits 0 to b-1, f[S] holds the sum over subsets that agree with S on every bit from b upward. Handling bit b then adds f[S without b] to f[S] for every S containing b. After all n bits, the constraint is gone.

def subset_sums(a, n):
    """f[mask] = sum of a[sub] over every sub that is a subset of mask."""
    f = list(a)
    for bit in range(n):                 # bit loop OUTSIDE, mask loop inside
        for mask in range(1 << n):
            if mask >> bit & 1:
                f[mask] += f[mask ^ (1 << bit)]
    return f

# a[s] = number of recipes whose required-ingredient set is exactly s
a = [0] * 8
for need in (0b001, 0b011, 0b011, 0b100, 0b111):
    a[need] += 1
print(subset_sums(a, 3))   # [0, 1, 0, 3, 1, 2, 1, 5]

A kitchen holding items 0 and 1 (mask 011) can cook 3 recipes; the full kitchen, all 5. The bit loop must be the outer loop. Swapping the loops silently double-counts subsets reachable along two paths, and the result is wrong without any error. Replacing + with - inverts the transform and recovers a from f.

Sizing: how big can n be

Before writing code, compute states, transitions and memory for your largest n.

A rough rule for a compiled language: around 10⁸ to 10⁹ simple operations per second per core. So add-one DPs fit up to about n = 22 to 25, submask DPs up to about n = 16 to 20, and an extra state dimension such as dp[mask][last] multiplies both time and memory by n. Python moves every limit down by several items. Measure on your own machine; these figures only decide whether to bother.

Memory is often the real wall: dp[mask][last] at n = 24 with 4-byte values needs about 1.5 GiB. Use flat arrays indexed by mask, never hash maps, and the narrowest value type that fits.

Failure modes

• Operator precedence. In C and C++, mask & 1 << j == 0 parses as mask & ((1 << j) == 0). Parenthesise every bit test.
• Shift overflow. 1 << 31 is negative in a 32-bit signed int and 1 << 32 is undefined behaviour in C. Use 1L << j or 1ULL << j whenever n can reach 31.
• Wrong evaluation order. Increasing integer order works when transitions only add bits. If your transition removes bits (dp[mask] built from larger masks), iterate downwards.
• Hidden order dependence. It is only correct when the future depends on the set alone. If the cost of the next step depends on the previous item, you need dp[mask][last]; if it depends on the whole order, bitmask DP does not apply.
• Infinity arithmetic. INT_MAX plus a cost overflows to a negative best answer. Skip unreachable states.

Trade-offs and alternatives

Bitmask DP gives exact answers at a predictable but exponential cost. Beyond about n = 25, consider meet in the middle for subset-sum style problems (2^n/2 per half, workable to about n = 40), branch and bound or an ILP solver when good bounds exist, a polynomial algorithm when the problem is exactly assignment, matching or flow, and heuristics when near-optimal is acceptable.

The other family of DPs that encode state in bits, digit DP and profile DP, use the mask for a different purpose: tight flags or the shape of a frontier rather than a chosen set. If your problem walks over number digits, Digit DP is the right tool.

What to do next

1. Write the brute force first, over permutations or subsets, and keep it as a test oracle.
2. State in one sentence what dp[mask] means, including whose turn it is or where you stand.
3. Classify the transition shape and size it for your largest n.
4. Implement with flat arrays, a parent array and 64-bit shifts; compare against brute force for n up to 8.
5. Guard against inputs above the n you sized for.
6. If the problem turns out to be plain assignment or matching, switch to the polynomial algorithm.