The idea: a subset is a number

Some problems need a DP state that says which items are already used. With n items there are 2ⁿ possible sets, and each one can be written as an n-bit number: bit j is 1 when item j is in the set. This number is the mask. The DP table is then a plain array indexed by the mask, and set operations become one machine instruction each. This is bitmask DP. It works when n is small, about 20 or less, and the order of the used items does not matter for the rest of the problem.

The eight subsets of the jobs J0, J1, J2 listed as numbers 0 to 7 with their bits: 0 = 000 is the empty set, 5 = 101 is {J0, J2}, 7 = 111 is all three jobs.
Every subset of 3 jobs is one of the numbers 0 … 7; bit j says whether job Jj is in it.

Bit tricks for set work

The page writes J0 as the right-most bit, so mask 13 = 8 + 4 + 1 = 1101 is the set {J0, J2, J3} (Demo 4: bit tricks on mask 1101).

set operationon the maskexample with 13 = 1101
is Jj in the set?mask >> j & 113 >> 1 & 1 = 0, 13 >> 2 & 1 = 1
remove Jjmask ^ (1 << j)13 ^ 4 = 9 = 1001
add Jjmask | (1 << j)13 | 2 = 15 = 1111
size of the setpopcount(mask)3
lowest membermask & -mask1, so J0
the full set(1 << n) - 115 = 1111

The assignment problem

n workers A, B, C, D must each get one of n jobs J0 … J3, and worker i doing job j costs c[i][j]. Find the cheapest way to hand out all jobs. Let the workers choose in the fixed order A, B, C, D. Then a set of taken jobs also tells how many workers are done: popcount(mask) of them. So dp[mask] is the cheapest way for the first popcount(mask) workers to take exactly the jobs in mask. The last of those workers took one of the jobs in mask; try each one.

dp[0] = 0                                   # no worker, no job
for mask = 1 … 2ⁿ − 1:                      # plain numeric order
    i = popcount(mask) − 1                  # the worker who took the last job
    dp[mask] = min over j in mask of dp[mask ^ (1 << j)] + c[i][j]
answer = dp[2ⁿ − 1]

On the canvas the mask being filled is orange, the masks it reads are blue, and the winner turns green. The edge of the winning choice stays dark, so the dark edges form a tree that the trace back follows from the full mask up to 0. On the 4-worker matrix the table ends with dp[1111] = 13: A → J1, B → J0, C → J2, D → J3 = 2 + 6 + 1 + 4 (Demo 2: 4 workers, all 16 masks).

Why numeric order is enough

A DP must fill a state after every state it reads. Here every read removes one bit, and removing a 1 bit always makes the number smaller. So the loop mask = 1, 2, 3, … is already a correct order. There is no need to group the masks by size, although the lattice on the canvas draws them that way to show the structure.

The 8 masks of 3 jobs drawn in rows by size, with an arrow from each mask with one bit removed to the mask itself. Every arrow goes from a smaller number to a bigger one, for example 1 to 3, 4 to 5 and 6 to 7.
Every arrow goes from a smaller number to a bigger one, so filling 0, 1, 2, … 7 in order never reads an empty cell.

How much work

There are 2ⁿ masks, and a mask with k bits does k additions, which sums to n·2ⁿ⁻¹. Brute force tries all n! orders. At n = 4 they are close (16 masks against 24 orders), but the factorial wins quickly after that.

norders n!masks 2ⁿadditions n·2ⁿ⁻¹
36812
4241632
103,628,8001,0245,120
202.4 × 10¹⁸1,048,57610,485,760

It is still exponential: every extra item doubles the table. For the assignment problem itself the Hungarian algorithm runs in O(n³), so bitmask DP is the tool for variants that break that structure, such as extra rules on which job may follow which. Held–Karp for the travelling salesman is the same idea with one more index: dp[S][j] needs the city j where the path stops, because the next cost depends on it. Here the next worker is fixed by popcount, so the mask alone is enough.

Greedy is not enough

A greedy rule lets each worker take the cheapest job still free. On the trap matrix A takes J0 for 1, but B is good only at J0 and now pays 8 for J2, and D is left with J3 for 8: 1 + 8 + 3 + 8 = 20. Bitmask DP finds A → J3, B → J0, C → J1, D → J2 = 3 + 2 + 3 + 2 = 10 (Demo 3: greedy 20 vs optimal 10). On the 4-worker matrix greedy pays 14 against 13, and on the 3-worker matrix it happens to tie at 12.

See also Subset Sum and 0/1 Knapsack, where the state is a running total instead of a set, and Permutations for the n! orders that brute force walks.

What the page leaves out

The Hungarian algorithm; iterating over all submasks of a mask (s = (s − 1) & mask, 3ⁿ in total); sum over subsets (SOS DP) and the subset convolution; profile DP over rows of a grid (broken profiles, tiling); meet in the middle for n around 40; and memory tricks such as storing only the masks of one size.