Skip to content
Tutorials Center
My learning

Topics

Lesson 158 of 225 ยท Dynamic Programming

Bitmask DP

Learn bitmask dynamic programming in Python: store subsets as integers, then solve the assignment problem, Held-Karp TSP and path counting step by step.

Some problems ask you to remember which items you have already used. Which cities has the salesperson visited? Which tasks are already assigned? Which of 15 switches are on? The state of the problem is not a number but a set. A set of n items has 2^n possible values, and if n is small (up to about 20), that is a perfectly fine number of DP states.

Bitmask DP stores each set as a single integer. Bit i of the integer is 1 when item i is in the set. Sets become array indexes, set operations become fast bit operations, and the whole dynamic programming toolbox (states, transitions, base case) carries over unchanged. In this lesson you will learn the bit tricks, then solve three classic problems: the assignment problem, the travelling salesperson problem (TSP) with the Held-Karp algorithm, and counting paths.

A set is an integer

Take three items, a, b, c, and give them bit positions 0, 1, 2. The integer 0b101 (5) means "bit 0 and bit 2 are on", so the set is {a, c}. Counting from 0 to 2^3 - 1 = 7 visits every subset exactly once.

TEXT
mask   bits (c b a)   subset
  0      0 0 0        { }
  1      0 0 1        { a }
  2      0 1 0        { b }
  3      0 1 1        { a, b }
  4      1 0 0        { c }
  5      1 0 1        { a, c }
  6      1 1 0        { b, c }
  7      1 1 1        { a, b, c }

Notice that the binary number reads right to left: item 0 is the rightmost bit. That is only a convention, but you should keep it consistent.

Python Enumerate every subset with a counter

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

1 << n shifts a 1 left by n places, which is 2**n. The test mask >> i & 1 shifts bit i down to position 0 and keeps only that bit (shifts bind tighter than & in Python).

The bit operations you need

Almost every bitmask solution uses these few expressions. If bit tricks are new to you, the lesson on bit manipulation goes deeper.

Goal Expression
Is item i in the set? mask >> i & 1
Add item i mask | (1 << i)
Remove item i mask & ~(1 << i)
Toggle item i mask ^ (1 << i)
Size of the set mask.bit_count()
The full set of n items (1 << n) - 1
Python Set operations on a mask

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Python integers never overflow, so 1 << 40 just works. Even so, a DP table with 2^n entries must fit in memory: n = 20 is about a million entries (fine), n = 25 is 33 million (too heavy for pure Python).

Example 1: the assignment problem

You have n people and n tasks. cost[p][t] is the price of giving task t to person p. Every person gets exactly one task and every task goes to exactly one person. What is the cheapest total?

Brute force. Try every permutation of tasks: n! assignments. That is 24 for n = 4 but 3,628,800 for n = 10 and far worse beyond.

Bitmask DP. Process people in order: person 0, then 1, and so on. The only thing that matters about the past is which tasks are taken, not who took which. So:

  • State: dp[mask] = cheapest cost to give the tasks in mask to the first mask.bit_count() people.
  • Transition: the next person is p = mask.bit_count(); try every free task t and move to mask | (1 << t).
  • Base case: dp[0] = 0. Answer: dp[full].
TEXT
people processed = number of 1 bits in mask

mask 0000  -> person 0 chooses a task  -> 0001, 0010, 0100, 1000
mask 0010  -> person 1 chooses a task  -> 0011, 0110, 1010
...
mask 1111  -> everybody has a task: answer
Python Assignment problem: brute force versus bitmask DP

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The DP has 2^n states, and each tries at most n tasks, so it runs in O(n * 2^n) time and O(2^n) space. For n = 12 that is about 24,000 transitions versus 479 million permutations. (For this particular problem a polynomial algorithm, the Hungarian algorithm, exists, but bitmask DP is the version you can write in five minutes and adapt when the rules get stranger.)

Example 2: travelling salesperson (Held-Karp)

A salesperson must visit every city exactly once, starting and ending at city 0, with the shortest total distance. Trying all orders costs (n-1)! tours. The Held-Karp algorithm, from 1962, does it in O(n^2 * 2^n).

The trick is the same: the future depends only on which cities are visited and where you are now, not on the order you visited them in.

  • State: dp[mask][j] = shortest path that starts at city 0, visits exactly the cities in mask (which always includes 0 and j), and ends at city j.
  • Base case: dp[1][0] = 0 (mask 0b1 is just city 0).
  • Transition: arrive at j from some k in mask without j: dp[mask][j] = min(dp[mask ^ (1<<j)][k] + dist[k][j]).
  • Answer: min(dp[full][j] + dist[j][0]) over all j.
Python Held-Karp TSP with the route rebuilt

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The code pushes forward from each reachable state (a "push" style) rather than pulling, which keeps the loops simple. Reconstructing the route is the usual DP trick: remember which j gave the best value (parent) and follow it back.

Complexity. There are 2^n * n states and each does O(n) work, so time is O(n^2 * 2^n) and space is O(n * 2^n). For n = 20 that is roughly 400 million simple steps: heavy in Python, comfortable in C++. For n = 15 it is quick. Compare that with 14! = 87 billion tours.

Example 3: counting with masks

Bitmask DP is not only for minimising. If you replace min with +, the same states count things. Here we count the Hamiltonian paths in a graph: paths that visit every vertex exactly once (a start anywhere, an end anywhere).

State: ways[mask][last] = number of paths that visit exactly the vertices in mask and end at last. Start with ways[1 << v][v] = 1 for every vertex v.

Python Counting Hamiltonian paths

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each undirected path is found twice (once in each direction), so we halve the count. The graph here is a 5-cycle with one chord, small enough to check against brute force. See also Eulerian and Hamiltonian paths.

Looping over submasks

Some problems split a set into two parts: "which subset goes in the first group?" To visit every non-empty submask sub of mask, use this loop:

TEXT
sub = mask
while sub > 0:
    use(sub)
    sub = (sub - 1) & mask

Subtracting 1 flips the lowest set bit and everything below it; & mask throws away bits that are not allowed. Over all masks together, this visits about 3^n pairs (mask, sub), because each item is either outside mask, inside mask but not sub, or inside both. That is why partition DPs like "split n people into teams" cost O(3^n).

Python Submask enumeration and the 3^n count

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Common mistakes

  • Precedence. In Python, mask & 1 << i works as mask & (1 << i) because shifts bind tighter, but mask & 1 == 0 parses as mask & (1 == 0). Parenthesise comparisons.
  • Forgetting the start. In TSP, mask 0b1 (only city 0) must be the base state; without it every state stays unreachable.
  • Visiting order bugs. When you push forward (dp[mask | bit]), masks must be processed in increasing order. A mask is always numerically larger than its subsets, so a plain range works.
  • Memory. [[INF] * n for _ in range(1 << n)] with n = 22 is 92 million cells. Know the limit before you start.
  • Using it too early. If the real constraint is n up to 100,000, the set is not the state. Look for another idea.

When to use bitmask DP

Reach for it when the constraint says n is about 20 or less and the problem is about subsets, permutations or "used/unused" flags: assignment, TSP, covering all items with the fewest groups, counting orderings with rules, and puzzle states like a small board. If you need more speed, meet in the middle can split a set of 40 items into two halves of 20.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. How many states does dp[mask] have for n items?

    Each of the n items is either in the set or not, so there are 2^n masks.
  2. 2. Which expression adds item i to mask?

    OR with a single set bit turns that bit on and leaves the others alone. AND tests a bit and XOR toggles it.
  3. 3. In the assignment DP, how do we know which person receives the next task?

    People are handled in order, so the number of tasks already taken equals the number of people already served.
  4. 4. What is the time complexity of Held-Karp for TSP?

    There are n * 2^n states (visited set, last city) and each tries up to n next cities.
  5. 5. Why does enumerating all submasks of all masks cost about 3^n?

    Three choices per item gives 3^n pairs (mask, sub).

Summary

  • A bitmask stores a subset of up to ~20 items as one integer, so a set can be a DP index.
  • Core operations: test mask >> i & 1, add | (1 << i), remove & ~(1 << i), size bit_count().
  • Assignment problem: dp[mask] over taken tasks, O(n * 2^n) instead of O(n!).
  • Held-Karp TSP: dp[mask][last], O(n^2 * 2^n) time, O(n * 2^n) space; keep parents to rebuild the route.
  • Swap min for + to count (Hamiltonian paths); iterate submasks with (sub - 1) & mask for partition DPs at O(3^n).
  • Use it only when n is small and the state really is a set.

Next: DP on Trees and DAGs