cf.completefrontend
DYNAMIC PROGRAMMING · ADVANCED

Bitmask DP

Use the bits of a number to record which items of a small set are already used, and keep a DP answer for every such set.

Time O(2ⁿ × n)Space O(2ⁿ)5 practice problemsStep-through picture

The idea

Some problems need to remember which items are already used, not just how many. With up to about 20 items, a set of items fits in the bits of one number, called a bitmask. Bit t is 1 if item t is in the set. For 3 items, the mask 0b101 (the number 5) means items 0 and 2 are used.

Bitmask DP keeps one answer per mask. Here best[mask] is the cheapest cost to assign the tasks in mask, one each, to the first few people. From each mask you try adding one more unused item, which gives a bigger mask.

There are 2^n masks, so this only works for small n: 2^20 is about a million, which is fine; 2^40 is not.

An everyday example

A seating chart with checkboxes

You are seating guests at a table one at a time and each guest has a different comfort score for each seat. A row of checkboxes shows which seats are taken. The next guest to seat is always the next one on the list, so the checkboxes alone tell you who is next. For every pattern of checkboxes, you write down the best total comfort to reach it.

How the example maps to the code
In the exampleIn the code
The row of checkboxesThe bits of mask
Seat t is takenmask & (1 << t) is not zero
How many guests are seatedcountBits(mask), the next person
Seating the next guest in seat tnext = mask | (1 << t)
Best total for a checkbox patternbest[mask]

From the slow way to bitmask dp

  1. Start with brute force: try every way to give each person one task, add up each assignment's cost, and keep the cheapest. With n people there are n! assignments: 3,628,800 for 10 people and 1,307,674,368,000 for 15.
  2. Build an assignment one person at a time, in a fixed order. After the first k people have a task, what matters for the rest? Only which tasks are taken. Whether person 0 took task 2 and person 1 took task 5, or the other way around, the remaining people face the same choices. So only the cheaper of those two beginnings is worth keeping.
  3. The state is the set of taken tasks. With n tasks there are 2^n sets, and each set fits in one number: bit t is 1 if task t is taken. Adding task t is mask | (1 << t), and checking it is mask & (1 << t). The number of 1 bits tells you how many people are done, so it also tells you who is next.
  4. Store best[mask], the cheapest cost to give the tasks in mask to the first few people. Go through masks from 0 upward, and from each reachable mask, try giving the next person each free task. Adding a bit always makes a bigger number, so every mask is final before the loop reaches it. That loop is bitmask DP.

How it works

  1. Make best with 2^n cells, all Infinity, and set best[0] = 0: no tasks assigned costs nothing.
  2. Go through masks from 0 upward. A mask's tasks are assigned to people 0 to countBits(mask) - 1, so person = countBits(mask) is next.
  3. Skip masks whose best is still Infinity; they can't be reached.
  4. For each task not in mask, form next = mask | (1 << task).
  5. Update best[next] with best[mask] + cost[person][task] if it is cheaper.
  6. The answer is best[full], where full has every bit set.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function minAssignCost(cost) {
  2. const n = cost.length;
  3. const full = (1 << n) - 1;
  4. const best = new Array(1 << n).fill(Infinity);
  5. best[0] = 0;
  6. for (let mask = 0; mask < full; mask++) {
  7. if (best[mask] === Infinity) continue;
  8. const person = countBits(mask);
  9. for (let task = 0; task < n; task++) {
  10. if (mask & (1 << task)) continue;
  11. const next = mask | (1 << task);
  12. best[next] = Math.min(best[next], best[mask] + cost[person][task]);
  13. }
  14. }
  15. return best[full];
  16. }
  18. function countBits(mask) {
  19. let count = 0;
  20. for (; mask; mask &= mask - 1) count++;
  21. return count;
  22. }

How fast it is

TimeO(2ⁿ × n)
Extra memoryO(2ⁿ)

Every one of the 2^n masks tries each of the n tasks once. The table has one cell per mask.

  • Best caseO(n · 2^n)

    Any cost table: from the empty mask every other mask is reachable, so every mask tries every task.

  • Average caseO(n · 2^n)

    Any cost table: 2^n masks, each checking n bits. For 15 people that is 491,520 steps.

  • Worst caseO(n · 2^n)

    The same. The costs never change which masks are visited, only which updates win.

Common mistakes

  • Using it for 30 or more items. 2^30 cells is about a billion; check that n is small first.
  • Writing mask & 1 << task === 0. In JavaScript === binds tighter than &, so add parentheses: (mask & (1 << task)) === 0.
  • Adding a person to the state when the mask already tells you who is next, which makes the table much bigger for no reason.
  • Using 1 << 31 or more. JavaScript's bit operators work on 32-bit signed numbers, so 1 << 31 is negative.

When to use it

Look for these clues in a problem:

  • The input has a small number of items, usually 20 or fewer.
  • The answer depends on which items were used, not just how many.
  • The question is about visiting every place once, assigning every task once, or covering every requirement.
  • A plain search over all orders (n!) is too slow, but 2^n * n is fine.

Check yourself

Answer each one in your head first, then open it.

Why does going through masks in increasing order work?

Adding a task sets a bit, which always makes a bigger number. So every update into a mask comes from a smaller mask, which the loop has already handled.

How does the code know which person is next?

It counts the 1 bits in mask. People are assigned in order, so k taken tasks means people 0 to k - 1 are done and person k is next.

In the trace, why does mask 101 drop from 10 to 9?

Two orders fill tasks 0 and 2: person 0 on task 0 and person 1 on task 2 cost 3 + 7 = 10, while person 0 on task 2 and person 1 on task 0 cost 4 + 5 = 9.

How many masks are there for 12 tasks?

2^12 = 4,096, from 0 (none taken) to 4,095 (all taken).

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 5 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The table keeps one promise: when the loop reaches mask, best[mask] is the cheapest cost to give exactly the tasks in mask to people 0 through k - 1, where k is the number of 1 bits. best[0] = 0 is right: no people, no tasks, no cost.

The promise holds because of where updates come from. A cheapest assignment for mask gives person k - 1 some task t in mask. The other people hold the tasks in mask without t, a smaller number, and they must be assigned as cheaply as possible; otherwise a cheaper arrangement could be swapped in. When the loop handled that smaller mask, it tried giving person k - 1 task t, so best[mask] has already seen the right value.

Every update goes from a mask to a strictly bigger one, so processing masks in increasing order means each mask has received every update before it pushes its own. Masks still at Infinity can't be reached and are skipped. The loop stops before full, and the promise says best[full] is the cheapest way to give all n tasks to all n people.

Going deeper

4 more ideas

What each cell means

best[mask] is the cheapest total cost to give the tasks in mask to people 0, 1, ..., k - 1, where k is the number of 1 bits in mask. The people are always taken in order, so the mask alone tells you who is next.

Why going through masks in increasing order works

Adding a task sets a bit, which always makes the number bigger. So every mask is only updated from smaller masks, and by the time the loop reaches a mask, all its updates are done.

How much work it does

There are 2^n masks and each tries n tasks, so the time is O(2^n * n) with O(2^n) space. For n = 15 that is about half a million steps. Trying every order instead would be 15!, more than a trillion.

Visiting every place (tours)

For the shortest route through every place, the state needs one more piece: where you are now. best[mask][last] is the shortest route that visits the places in mask and ends at last. That is O(2^n * n^2) time.

Work it by hand

Every step in a table, with why

Give 3 people one task each at the least total cost. Masks are written with task 2 on the left, so 001 means only task 0 is taken. Each row is one update.

cost = [[3, 8, 4], [5, 2, 7], [6, 9, 3]], where row p is person p

Stepmaskbest[mask]persontasknextbest[next]What happensWhy
1000000001∞ to 3First optionFrom the empty mask, person 0 takes task 0 for 3.
2000001010∞ to 8Person 0, task 1Person 0 takes task 1 for 8.
3000002100∞ to 4Person 0, task 2Every one-task mask is now reachable.
4001311011∞ to 53 + 2One bit is set, so person is 1. Task 0 is taken, so person 1 tries tasks 1 and 2.
5001312101∞ to 103 + 7A first value for mask 101, which a later row will beat.
60108100115, keep 58 + 5 = 13 losesLine 12 keeps the smaller value. The other order of tasks 0 and 1 was cheaper.
7010812110∞ to 158 + 7A first value for mask 110.
8011522111∞ to 85 + 3Two bits set, so person 2 is next, and only task 2 is free. The full mask gets its first value.
910041010110 to 94 + 5 is betterPerson 0 on task 2 and person 1 on task 0 beat the earlier way to fill tasks 0 and 2.
1010041111015 to 64 + 2 is betterA big drop: person 1 is cheap on task 1.
111019211118, keep 89 + 9 = 18 losesPerson 2 is expensive on task 1.
121106201118, keep 86 + 6 = 12 losesThe last update. The loop stops before mask 111, since mask < full is false.

It returns 8: person 0 on task 0, person 1 on task 1, person 2 on task 2, for 3 + 2 + 3. The loop ends when mask reaches full, because the full mask has no free task to add.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Bitmask DPO(n · 2^n)O(2^n)Up to about 20 items, when the answer depends on which items are used, not on their order.
Try every orderO(n!)O(n)Only for about 10 items or fewer, or as a check.
Hungarian algorithmO(n³)O(n²)Pure assignment problems with many people, such as 500. It solves this exact problem much faster, but doesn't generalize to tours or groups.
Backtracking with pruningO(n!)O(n)When good bounds cut most branches early. Its worst case stays factorial.

Extra memory: O(2^n) for best: about a million numbers for 20 tasks. That memory limit is usually what stops bitmask DP, not the time.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Bitmask DP and the other approaches, on a scale where each line up is 10 times more steps.
  • Bitmask DP O(n · 2^n)
  • Try every order, Backtracking with pruning O(n!)
  • Hungarian algorithm O(n³)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Bitmask DP10,240more than a quadrillionmore than a quadrillion
Try every order4 millionmore than a quadrillionmore than a quadrillion
Hungarian algorithm1,0001 billionmore than a quadrillion
Backtracking with pruning4 millionmore than a quadrillionmore than a quadrillion

Inputs that need care

5 tricky inputs
No people: cost = []
full is 0, so the loop never runs, and it returns best[0], which is 0.
One person: cost = [[6]]
Mask 0 tries task 0 and sets best[1] = 6. The loop stops at full = 1 and returns 6.
A forbidden pairing, written as Infinity
best[mask] + Infinity is Infinity, so it never wins. If every full assignment is forbidden, it returns Infinity; turn that into -1 if the problem wants that.
Ties between assignments
Math.min keeps the cost, and any tied assignment is fine. To report the assignment, keep the first one found, or decide on another rule.
31 or more tasks
1 << 31 is negative in JavaScript, and 2^31 cells won't fit in memory anyway. Bitmask DP is for about 20 items or fewer.

Variations and follow-ups

Twists interviewers add

Shortest tour through every place

For a route that visits every place once, the next step depends on where you are, so the state is best[mask][last]. Each state tries every unvisited place, which gives O(2^n · n²) time.

Looping over submasks

Some problems split a set into groups. For each mask, loop over its submasks with sub = (sub - 1) & mask. Across all masks, that is 3^n steps in total, which is fine for n up to about 15.

More people than tasks, or the reverse

Put the smaller side in the mask. If there are 8 tasks and 50 people, loop over people one at a time and keep best[mask] for which tasks are filled, letting each person take one free task or none.

Memoized version

Write solve(mask) that tries every free task for the next person and caches the result. It only visits reachable masks, which helps when many masks are impossible.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from a tiny limit, like n ≤ 16 or n ≤ 20, together with "each item used once" or "visit every place". A limit that small is a strong hint that 2^n is expected.
  • Explain the mask in one sentence: "bit t is 1 if task t is taken". Then say why the person doesn't need to be in the state: the number of 1 bits tells you who is next.
  • Test a 2 by 2 cost table by hand, where you can list both assignments, and check that the increasing mask order fills 11 last.
  • Expect "how much memory?" and "how far can n go?". 2^20 cells is about a million numbers, fine; 2^30 is a billion, too many. Also mention that JavaScript bit operators stop working at 31 bits.

Where frontend code uses it

The same idea in real UI code
  • Route planners that order a handful of stops, such as a delivery app with 10 drops, can find the shortest order with a bitmask table.
  • Assigning a few reviewers to a few pull requests, or a few people to shifts, with the least total cost fits this table.
  • Feature flags are often stored as bits in one number, the same representation bitmask DP uses for sets.

Related algorithms