Bitmask DPBitmask DP

01Why it exists

Reach for it when you see:n ≤ 20, each element either used or unused, visit every point once (TSP), assignment, cover every requirement, the state is a set, dp[mask], dp[mask][last], 2ⁿ states.

02The core idea

In some problems the decisions that follow depend on which things have already been used, not merely how many: TSP needs to know which cities you have visited, and the assignment problem needs to know which jobs have been taken. That set is itself the state. When there are few elements, encode the set as an n-bit integer mask, where bit i being 1 means element i is in the set. The 2ⁿ possible sets then map onto the integers 0 through 2ⁿ − 1 and can index an array directly. That is bitmask DP. Adding an element is mask | (1 << i), testing one is mask >> i & 1, and both are O(1) bit operations (the toolkit from the Subset Enumeration lesson).

Take TSP: dp[mask][j] is the cheapest way to start at 0, visit exactly the cities in mask, and end standing at j. Why j has to be part of the state: how far you still have to travel depends on where you are now, and the mask alone does not say. But as long as mask and j match, how you got there has no bearing on what comes next, so of two paths reaching the same state you only need to keep the cheaper one — that is the optimal substructure. The transition is dp[mask | (1 << k)][k] = min(dp[mask][j] + d[j][k]) over cities k not yet visited; once every city is covered, add the distance back to 0 and take the minimum. As for fill order, adding an element only ever makes the integer larger, so a single sweep with mask in ascending order guarantees that every state you read has already been computed.

Complexity: TSP has 2ⁿ·n states and tries n next stops from each, so O(2ⁿ·n²) time and O(2ⁿ·n) space. At n = 16 that is about 1.7×10⁷ operations; at n = 20 it is about 4.2×10⁸ and the table needs 2²⁰×20 integers (80 MB), which is roughly the ceiling. The assignment problem can derive "which person comes next" from the number of 1 bits in the mask, so the state is just the mask: O(2ⁿ·n). Compare that with brute force: at n = 20 there are 20! ≈ 2.4×10¹⁸ permutations. Bitmask DP turns a factorial into an exponential times a polynomial, but it is still exponential — TSP is NP-hard, and past this size you are left with approximation or heuristics.

Common traps: in C++ the comparison operators bind tighter than &, so mask & 1 << j == 0 actually means mask & ((1 << j) == 0) — always parenthesise bit operations. Forgetting to pin the start means a TSP that does not begin at 0 computes redundant states and can give a wrong answer. INF values can overflow when added. And building a 2ⁿ table anyway when n exceeds 20 runs out of memory first. The transitions can be written either as a push (dp[mask] updates larger masks) or as a pull (dp[mask] is computed from the subsets with one element removed); the two are equivalent. When a transition has to split a mask into two subsets, you need subset enumeration, which sums to 3ⁿ over all masks. Shortest Path Visiting All Nodes, meanwhile, runs BFS over a state graph of (mask, node) — the same state design, solved with graph theory instead.

03The algorithm

1. 1Confirm the size is small (n up to about 20) and that later decisions depend on which elements have been used.
2. 2Define the state: dp[mask], or dp[mask][j] when you also need to know the last element. Bit i stands for element i.
3. 3Set the base case, such as dp[1][0] = 0 for TSP (only start city 0 visited) or dp[0] = 0 for assignment.
4. 4Sweep mask in ascending order. For each reachable state, try adding an unused element k and update the next state via mask | (1 << k), recording a parent if you need to reconstruct the solution.
5. 5The answer sits at the full set (1 << n) − 1. For TSP, add the edge back to the start and take the minimum; following the parents backwards gives the route.

04Interactive demo

A complete distance graph on 4 cities, starting at city 0, visiting each city once and returning to 0. The table on the right lists the 8 masks that contain the start; each cell dp[mask][j] is the cheapest way to cover mask and stop at j, and the masks are filled in ascending order. Filling one cell means checking every possible previous stop: blue in the table is the state being filled, yellow is the dp[mask without j][previous] it reads. The graph on the left follows along, marking the current position blue, the previous stop yellow, and the cities already in the mask green, with the edge under consideration drawn in blue. Once every city is covered, add the distance back to 0: the shortest tour is 80, along 0 → 2 → 3 → 1 → 0. That last step is also why DP beats enumerating permutations as n grows.

05Code

Python has the "push" form of TSP (including route reconstruction) and the assignment problem, which needs only the mask and never the last position. C++ has the "pull" form of TSP, matching the interactive demo, plus the fewest-hires staffing cover: the state is the set of days already staffed, and each hire ORs in the days they can work.

from math import inf


def tsp(dist):
    """Shortest tour from 0 visiting every city once and returning to 0, plus the route. O(2ⁿ·n²)"""
    n = len(dist)
    FULL = 1 << n
    dp = [[inf] * n for _ in range(FULL)]         # dp[mask][j]: min cost to cover mask and stop at j
    parent = [[-1] * n for _ in range(FULL)]
    dp[1][0] = 0                                  # only 0 visited, standing at 0
    for mask in range(FULL):                      # ascending: adding a city only grows the integer
        if not mask & 1:
            continue                              # every tour starts at 0
        for j in range(n):
            if dp[mask][j] == inf:
                continue
            for nxt in range(n):                  # push forward: from (mask, j) to an unvisited nxt
                if mask >> nxt & 1:
                    continue
                new = mask | 1 << nxt
                if dp[mask][j] + dist[j][nxt] < dp[new][nxt]:
                    dp[new][nxt] = dp[mask][j] + dist[j][nxt]
                    parent[new][nxt] = j
    last = min(range(1, n), key=lambda j: dp[FULL - 1][j] + dist[j][0]) if n > 1 else 0
    best = dp[FULL - 1][last] + dist[last][0]
    route, mask, j = [], FULL - 1, last
    while j != -1:                                # walk back along parent, clearing j from mask
        route.append(j)
        mask, j = mask ^ (1 << j), parent[mask][j]
    return best, route[::-1] + [0]


def min_assignment(cost):
    """cost[i][j]: person i doing job j. Pick a job for person 0, 1, 2...; mask holds taken jobs"""
    n = len(cost)
    dp = [inf] * (1 << n)
    dp[0] = 0
    for mask in range(1 << n):
        i = bin(mask).count("1")                  # people assigned so far, so person i comes next
        if i == n:
            continue
        for j in range(n):
            if not mask >> j & 1:
                dp[mask | 1 << j] = min(dp[mask | 1 << j], dp[mask] + cost[i][j])
    return dp[(1 << n) - 1]


if __name__ == "__main__":
    dist = [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]]   # same as the demo
    print(tsp(dist))                              # (80, [0, 2, 3, 1, 0])
    print(min_assignment([[9, 2, 7, 8], [6, 4, 3, 7], [5, 8, 1, 8], [7, 6, 9, 4]]))   # 13 (2 + 6 + 1 + 4)

06Practice

• LeetCode 526Beautiful Arrangement (mask is the numbers used, the next position is the popcount)Medium
• LeetCode 1986Minimum Number of Work Sessions to Finish the Tasks (mask is the finished tasks)Medium
• LeetCode 698Partition to K Equal Sum Subsets (dp[mask] tracks how full the current bucket is)Medium
• LeetCode 1879Minimum XOR Sum of Two Arrays (the assignment problem in disguise)Hard
• LeetCode 847Shortest Path Visiting All Nodes (BFS over (mask, node))Hard
• LeetCode 943Find the Shortest Superstring (TSP with overlap length as the distance)Hard