Chapter 7: Bitmask DP

Some problems require tracking which elements have been used from a small set. When n ≤ 20, you can encode any subset as an integer bitmask — a single int where bit i is 1 if element i is included. This compresses an exponential set of subsets into a number you can iterate over, and it unlocks DP states like dp[mask] or dp[mask][i].

Bitmask DP appears in assignment problems, traveling salesman, Hamiltonian paths, subset sum with extra structure, and any problem where the state is “which items are chosen so far.”

Bit Manipulation Primer

You need a handful of operations. Treat them as vocabulary — they appear in every bitmask DP solution.

Check if bit i is set:     mask & (1 << i)
Set bit i:                 mask | (1 << i)
Clear bit i:               mask & ~(1 << i)
Toggle bit i:              mask ^ (1 << i)
Count set bits:            __builtin_popcount(mask)   // C++
                           bits.OnesCount(uint(mask)) // Go

Iterate all submasks of mask:
  for (sub = mask; sub; sub = (sub - 1) & mask)

Iterate all masks of size n:
  for (mask = 0; mask < (1 << n); mask++)

Traveling Salesman Problem

The classic Held-Karp algorithm: visit every city exactly once, starting and ending at city 0, with minimum total distance. State dp[mask][i] = minimum cost to visit all cities in mask, ending at city i.

Worked Example: 4 Cities

Consider cities 0–3 with distances:

     0   1   2   3
0 [  0  10  15  20 ]
1 [ 10   0  35  25 ]
2 [ 15  35   0  30 ]
3 [ 20  25  30   0 ]

Start at city 0. Base: dp[0001][0] = 0 (only city 0 visited).

From mask=0001 (city 0), extend to city 1:
  dp[0011][1] = dp[0001][0] + dist[0][1] = 10

Continue filling by increasing popcount of mask.
When mask = 1111 (all visited), try ending at each city i,
then add dist[i][0] to return home.

Optimal tour: 0 → 1 → 3 → 2 → 0, cost = 10 + 25 + 30 + 15 = 80.

A full 2ⁿ × n table is too large to visualize interactively — that is why we trace a small 4-city example by hand instead of using the table visualizer. The pattern is the same at any scale.

Assignment Problem

Assign n workers to n tasks (one-to-one). cost[i][j] is the cost of worker i doing task j. Find the minimum total cost.

State dp[mask] = minimum cost to assign the first popcount(mask) tasks, using exactly the workers whose bits are set in mask. The next task index equals the number of set bits. Try each unused worker for that task.

dp[0] = 0
task = popcount(mask)
for each worker w not in mask:
    dp[mask | (1<<w)] = min(..., dp[mask] + cost[w][task])

Answer: dp[(1<<n) - 1]

Summary

• When: track subsets of ≤ 20 elements
• State: dp[mask] or dp[mask][i]
• Transition: add one element to the mask, or extend from a submask
• Iteration: by increasing popcount, or all masks 0..2ⁿ−1
• Time: typically O(n² · 2ⁿ) or O(n · 2ⁿ)