Bitmask DP over subsets

39 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Three workers, three jobs, and a cost table. Each worker takes exactly one job. Which assignment is cheapest?

By hand you would list the orders: job 0 to worker 0, job 1 to worker 1, job 2 to worker 2; then job 0 to worker 0, job 1 to worker 2, job 2 to worker 1; and so on. For 3 workers there are 3 × 2 × 1 = 6 orders. For 10 workers there are 3,628,800, and for 20 there are about 2.4 × 10¹⁸. Orders explode because they remember who got which job in which sequence, which is more than needed.

Build the structure, one piece at a time

What actually matters after placing some jobs is only which workers are already busy, not the order in which they became busy. Record that as a row of bits, one per worker: 1 for busy, 0 for free. With three workers the row is three bits, written as a binary number called a mask. 000 means nobody is busy, 101 means workers 0 and 2 are busy. There are 2³ = 8 masks.

The number of 1 bits in the mask (its popcount) tells you how many jobs are already placed, so the next job to place is job number popcount(mask). Keep one number per mask: dp[mask] = cheapest cost of placing the first popcount(mask) jobs on exactly the workers in mask. Fill masks in increasing order; each mask is reached by adding one worker to a smaller mask.

1. dp[000] = 0: nothing placed, nothing paid.
2. One bit set, job 0 placed: dp[001] = 9 (worker 0), dp[010] = 2 (worker 1), dp[100] = 7 (worker 2).
3. Two bits set, job 1 placed on the newest worker: dp[011] = min(dp[010] + 6, dp[001] + 4) = 8; dp[110] = min(dp[100] + 4, dp[010] + 3) = 5; dp[101] = min(dp[100] + 6, dp[001] + 3) = 12.
4. All three bits, job 2: dp[111] = min(dp[110] + 5, dp[101] + 8, dp[011] + 1) = min(10, 20, 9) = 9.

Cheapest total: 9, with job 0 on worker 1, job 1 on worker 2, job 2 on worker 0.

Why it is correct

The invariant: dp[mask] is the true cheapest way to place the first popcount(mask) jobs on exactly the workers in mask. Any such placement gave the latest job to some worker w in mask; removing w leaves a valid placement of the earlier jobs on mask without w, whose cost is at least dp[mask − w] by the invariant. So the best for mask is the minimum over w in mask of dp[mask without w] + cost of the latest job on w, which is exactly what the loop computes. Order among the earlier jobs never matters, because the cost is a sum.

dp[mask] = min over bits w in mask of ( dp[mask ⊕ 2^w] + cost[popcount(mask) − 1][w] )

Why it is fast

There are 2ⁿ masks and each looks at up to n bits, so the work is O(2ⁿ · n). For 20 workers that is about 21 million steps, against 2.4 × 10¹⁸ orders. The gain comes from collapsing every order with the same set of busy workers into one table cell. Memory is 2ⁿ numbers, which is why this pattern appears only when n is about 20 or less.

How to recognise it in an interview

Cues: a small n (at most about 20), "every item exactly once", "visit all", "assign", or subsets. Say: the state is the set of items used, which fits in an integer of n bits. Shortest Path Visiting All Nodes stores (mask of visited nodes, current node). Partition to K Equal Sum Subsets asks, for each mask of used numbers, whether the current bucket can be filled. Parallel Courses II uses the mask of finished courses and adds up to k courses per step.

02The idea in one line

The mask records which items are used; add one item per transition.

Reach for it when: Shortest path visiting all nodes, partition to k subsets, parallel courses II, minimum XOR sum.

Cost: O(2^n · n) time.

03The walk-through, step by step

The video works one example: Assign 3 jobs to 3 workers by mask. These are its captions in order, so you can follow without the video or check a step you missed.

1. A mask of workers already used; its popcount says how many jobs are placed
2. mask 001 → job 0: min(dp[000]+9) = 9
3. mask 010 → job 0: min(dp[000]+2) = 2
4. mask 011 → job 1: min(dp[010]+6, dp[001]+4) = 8
5. mask 100 → job 0: min(dp[000]+7) = 7
6. mask 101 → job 1: min(dp[100]+6, dp[001]+3) = 12
7. mask 110 → job 1: min(dp[100]+4, dp[010]+3) = 5
8. mask 111 → job 2: min(dp[110]+5, dp[101]+8, dp[011]+1) = 9
9. dp[111] = 9: job0→w1 (2), job1→w2 (3), job2→w0 (5)
10. 2ⁿ masks, n transitions each: O(2ⁿ · n) instead of n! orderings

04Asked at Google

6 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Dynamic Programming: 1-D linear DP, Kadane (best ending here), Longest increasing subsequence, Grid path DP, 0/1 knapsack (subset sum), Unbounded knapsack (coin change), Two-sequence DP (LCS / edit distance), Wildcard / regex matching DP, Palindromes: expand or table, Prefix segmentation DP, Interval DP (last operation), State-machine DP (stocks), Memoised DFS (top-down), Digit DP, Game DP (minimax on a range), Counting ways with modulo, DP over sorted keys (chains).