Bitmask DP: Subsets, Assignments and Row Profiles

Bitmask DP stores "which of the n items are already used" as an n-bit integer and runs dynamic programming over those subsets. It turns n! orderings into 2^n subsets, which is exactly the jump that makes n up to about 20 tractable.

Intuition

Brute force over orderings (which city next, which worker gets which job) costs n!. But the future usually does not care about the order in which items were used, only which ones were used, plus maybe the last one. Encode that set as an integer whose bit i is 1 when item i is used, and the state space shrinks to 2^n (times n if you also need the last item). Transitions add one item (mask | 1 << i) or a whole group (a submask), so every transition goes from a smaller integer to a larger one, and iterating masks in increasing numeric order is a valid order.

Operation	Python
Is item i in the set?	mask >> i & 1
Add item i	mask | 1 << i
Remove item i	mask & ~(1 << i)
Number of items	mask.bit_count()
Lowest item	(mask & -mask).bit_length() - 1
All non-empty submasks	s = mask; while s: ...; s = (s - 1) & mask

When to use it in interviews / OAs

• n is small (n <= 20, sometimes <= 16) and the problem is about orderings, assignments or partitions.
• "Visit every node / use every word / assign every task" with a cost that depends on what was done before.
• A grid with a tiny width (<= 10) where each row's choice only interacts with the previous row.
• A game where the state is "which numbers or items have been taken".

Template 1: subset + last element (shortest Hamiltonian path)

f[mask][v] = the shortest path that visits exactly the nodes in mask and ends at v. Extend it by any unvisited u.

def shortest_hamiltonian_path(dist: list[list[int]]) -> int:
    n = len(dist)
    INF = float("inf")
    full = 1 << n
    # f[mask][v] = shortest path visiting exactly the nodes in mask, ending at v
    f = [[INF] * n for _ in range(full)]
    for v in range(n):
        f[1 << v][v] = 0  # a path can start anywhere
    for mask in range(full):  # transitions only add bits, so smaller masks are done first
        for v in range(n):
            cur = f[mask][v]
            if cur == INF:
                continue
            for u in range(n):
                if not mask >> u & 1:
                    nxt = mask | 1 << u
                    if cur + dist[v][u] < f[nxt][u]:
                        f[nxt][u] = cur + dist[v][u]
    return min(f[full - 1])

For a closed tour (traveling salesman), fix the start at node 0 (f[1][0] = 0 only) and finish with min(f[full-1][v] + dist[v][0]).

Template 2: assignment (the k-th item goes next)

When items are assigned in a fixed order (worker 0, then worker 1, ...), the number of set bits already tells you whose turn it is, so the state is just the mask.

def min_assignment_cost(cost: list[list[int]]) -> int:
    n = len(cost)
    INF = float("inf")
    # f[mask] = best cost after workers 0..popcount(mask)-1 took exactly the jobs in mask
    f = [INF] * (1 << n)
    f[0] = 0
    for mask in range(1 << n):
        if f[mask] == INF:
            continue
        i = mask.bit_count()  # the next worker to assign
        if i == n:
            continue
        for j in range(n):
            if not mask >> j & 1:
                nxt = mask | 1 << j
                f[nxt] = min(f[nxt], f[mask] + cost[i][j])
    return f[(1 << n) - 1]

This is O(2^n * n), much better than O(n!) and easy to adapt to "maximize compatibility" or "minimize the XOR sum".

Template 3: partition into groups (submask enumeration)

People cross a bridge in groups, one group at a time. A group's total weight must stay within the limit, and it needs as long as its slowest member. Minimize the total time. f[mask] = least time to get everyone in mask across; the last group is some non-empty submask s of mask.

def min_total_time(weights: list[int], times: list[int], limit: int) -> int:
    n = len(weights)
    full = 1 << n
    w_sum, t_max = [0] * full, [0] * full  # total weight and slowest time of every subset
    for mask in range(1, full):
        low = mask & -mask
        i = low.bit_length() - 1
        rest = mask ^ low
        w_sum[mask] = w_sum[rest] + weights[i]
        t_max[mask] = max(t_max[rest], times[i])
    INF = float("inf")
    f = [INF] * full  # f[mask] = least total time to get everyone in mask across
    f[0] = 0
    for mask in range(1, full):
        s = mask
        while s:  # every non-empty submask of mask can be the last group
            if w_sum[s] <= limit:
                f[mask] = min(f[mask], f[mask ^ s] + t_max[s])
            s = (s - 1) & mask
    return f[full - 1]

Precomputing per-subset values with the "remove the lowest bit" recurrence costs O(2^n). Enumerating the submasks of every mask costs O(3^n) in total, because each element is either outside the mask, in the mask but not in the submask, or in both. 3^16 is about 43 million, so this pattern is good up to n of about 15-16 in Python.

Template 4: row-by-row profile

Choose usable cells in a grid so that no two chosen cells share an edge, and count the choices. The width is small, so a whole row fits in a mask. A row mask is valid if it has no two adjacent bits (m & (m << 1) == 0), avoids unusable cells, and shares no bit with the previous row.

def count_independent_cells(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    # row masks without two horizontally adjacent cells
    valid = [m for m in range(1 << cols) if m & (m << 1) == 0]
    ways = {0: 1}  # ways[m] = fillings of the rows so far whose last row is m
    for r in range(rows):
        usable = sum(1 << c for c in range(cols) if grid[r][c])
        nxt = {}
        for m in valid:
            if m & ~usable:
                continue
            total = sum(cnt for prev, cnt in ways.items() if prev & m == 0)
            if total:
                nxt[m] = total
        ways = nxt
    return sum(ways.values())

Only about 1.6^cols masks are valid, so even width 10 has just 144 of them.

Complexity

Pattern	Time	Space
Subset + last element	O(2^n * n^2)	O(2^n * n)
Assignment	O(2^n * n)	O(2^n)
Submask partition	O(3^n)	O(2^n)
Row profile	O(rows * V^2), V = valid row masks	O(V)

A related tool, sum over subsets (SOS) DP, computes an aggregate over all submasks of every mask in O(n * 2^n) by adding one bit dimension at a time.

Common pitfalls

• n too large: 2^20 * 20 states is 20 million entries; that is heavy for Python lists. Check the constraint before committing.
• Operator precedence in C++/Java: mask & 1 << i == 0 parses as mask & ((1 << i) == 0). Always parenthesize. (Python's precedence makes mask >> i & 1 safe, but parentheses never hurt.)
• Submask loop that never ends: s = (s - 1) & mask must stop at 0; handle the empty submask separately if you need it.
• Wrong iteration order: iterating masks in increasing order is valid only when transitions add bits. If they remove bits, iterate downward.
• Forgetting the last element: if the cost of adding an item depends on the previous item (distances, overlaps), the state must include it.
• Counting the same partition twice: when counting partitions, force the submask to contain the lowest set bit of mask.

Interview variations

• Shortest path visiting all nodes (BFS over (mask, node) when edges are unweighted), shortest superstring (overlap costs between words).
• Minimum XOR sum of two arrays, maximum compatibility score, assigning tasks to workers: assignment DP.
• Partition into k equal-sum subsets, fair distribution of cookies, minimum work sessions: subset states, often with submask enumeration.
• Can the first player win when players take numbers from a shared pool: memoized game over the mask of taken numbers.
• Seating students so that nobody can cheat, placing non-attacking pieces: row-by-row profile.
• Ways for people to choose distinct hats: iterate over hats, keep the mask of people who already have one.