Bitmask DP

Delivery routes, chip drilling, scheduling small teams: when the state has to remember which of n things are already done, store that set as the bits of an integer. For n up to about 20 this turns n! brute force into something that runs in a second.

advanced⏱ 12 min read

←Builds on

9Bit ManipulationThe set of visited cities is stored as a bitmask, tested and extended with the bit tricks you just learned.10DP Fundamentals: Memo & TableMemoising over subsets turns n! tours into 2ⁿ·n states.10Floyd–Warshall: DP on GraphsThe salesman needs distances between every pair of cities, which Floyd–Warshall provides.

Leads to→

12P vs NP & Choosing an AlgorithmBitmask DP solves the salesman in O(2ⁿ·n²): better than n!, still exponential, which is what NP-hard looks like.

1Learn 2Play 3Check 4Practice

Learn

The idea, the mechanics and the cost.

01A subset is just an integer

Number the items 0..n−1. A subset is an n-bit number: bit j is 1 when item j is in the set. With 4 cities, 1011₂ = 11 means cities 1, 2 and 4 (bits 0, 1, 3).

All set operations become one CPU instruction:

is j in the set? mask & (1 << j)
add j: mask | (1 << j); remove j: mask & ~(1 << j)
the full set: (1 << n) − 1; all subsets: for mask in 0 .. 2ⁿ−1

So an array indexed by mask, dp[mask], stores one answer per subset: 2ⁿ entries. For n = 20 that is about a million, comfortable. For n = 30 it is a billion, too many. That limit tells you when to think of bitmask DP: the constraints say n ≤ 20 or so, and the problem needs to remember “which ones are used”.

Note that if mask′ adds an element to mask, then mask′ > mask, so increasing order is a valid fill order.

02Travelling salesman with dp[mask][i]

Visit every city exactly once and return to the start, minimising total distance. Brute force tries (n−1)! orders.

The key observation: once you have visited a set of cities and stand at city i, the order you visited them in no longer matters for the rest of the trip. So the state is

dp[mask][i] = the cheapest path that starts at city 1, visits exactly the cities in mask, and ends at i.

base: dp[{1}][1] = 0;
transition: from (mask, i) go to an unvisited j: dp[mask | j][j] = min(…, dp[mask][i] + D[i][j]);
answer: min over i of dp[full][i] + D[i][1], closing the loop.

For the 4 cities in the figure the best tour is 1 → 2 → 4 → 3 → 1 = 10 + 25 + 30 + 15 = 80. Store the predecessor of each state to print the route.

03Exponential, but far less so, and a glimpse of NP

There are 2ⁿ·n states and each tries n next cities, so the time is O(2ⁿ·n²) with O(2ⁿ·n) memory. For n = 20 that is about 4·10⁸ simple steps, a second or two in C++. Brute force would need 20! ≈ 2.4·10¹⁸.

It is still exponential, and that is no accident. TSP is NP-hard: nobody knows a polynomial algorithm, and finding one would prove P = NP. Bitmask DP is the honest best for exact answers on small n. For larger inputs, practice switches to heuristics and approximations, which is where the capstone stage picks up.

The same pattern solves many “assign / order a small set” problems: Hamiltonian paths, assigning n workers to n jobs, packing items into the fewest trips, and more. When you see n ≤ 20, try writing the state as dp[mask] or dp[mask][last].

Cost at a glance

TSP with bitmask DPO(2ⁿ·n²)

MemoryO(2ⁿ·n)

Brute force over all toursO(n!)

Remember

A subset of n ≤ ~20 items fits in an integer’s bits, so dp[mask] stores one answer per subset.
For TSP, “which cities are visited” plus “where am I now” is all the future needs, giving dp[mask][i].
O(2ⁿ·n²) beats n! enormously but is still exponential, as expected for an NP-hard problem.

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: Rows are masks (which cities are visited), columns the city you end at. Watch cells fill from small masks to the full 1111 row, then the tour closes back to city 1.

Interactive visualizerfocus here, then space ← →

Bitmask DP: TSP (4 cities, start 1)

mask\\end	1	2	3	4
0001	0	·	·	·
0011	·	·	·	·
0101	·	·	·	·
0111	·	·	·	·
1001	·	·	·	·
1011	·	·	·	·
1101	·	·	·	·
1111	·	·	·	·

Travelling Salesman: visit every city once and return, at minimum cost. State = (which cities visited as a bitmask, current city). Base: at city 1 alone, cost 0.

Pseudocode

 1 dp[mask][i] = cheapest path from city 1 visiting exactly `mask`, ending at i 2 base: dp[{1}][1] = 0 3 transition: dp[mask|1<<j][j] = min over i in mask of dp[mask][i] + D[i][j] 4 answer = min over i of dp[full][i] + D[i][1]   // close the tour

1 / 1

Check

Three questions. Pick an answer to see why.

With 5 items, which mask is the set {0, 2, 4}?

Why can dp[mask][i] forget the order in which the cities in mask were visited?

Roughly how many dp[mask][i] states are there for n = 16?

Practice

Real problems to lock it in, easiest first.

LeetCodeSubsets intermediate↗LeetCodePartition to K Equal Sum Subsets intermediate↗CSESHamiltonian Flights advanced↗LeetCodeShortest Path Visiting All Nodes advanced↗CSESElevator Rides advanced↗