Bitmask DP
In one line
When the state of a DP must remember which of up to about 20 items are already used, store that set as a bitmask, turning n! orderings into about 2^n states.
What it is
Bitmask DP is dynamic programming where part of the state is a bitmask recording which items have been used, visited or assigned. A typical state is dp[mask] or dp[mask][i], where mask is the set used so far and i is the last item chosen.
It works because many problems only care about which items are used, not the order they were used in. Trying every order of 15 cities is 15!, about 1.3 trillion. With bitmask DP there are only 2^15 = 32,768 sets times 15 last cities, so the classic travelling salesman algorithm (Held-Karp) runs in O(n^2 * 2^n) instead of O(n!).
Why interviewers ask
It is the standard technique for hard-looking problems with small n: assignment, travelling salesman, visiting all nodes, partitioning into equal groups. Interviewers look for the moment you notice n is at most 15 to 20 and realise the state can be a set, then for a clear state definition, transition and complexity.
How it works
- 1Spot the signal: n is small (usually at most 20) and the answer depends on which items have been used.
- 2Define the state. For assignment, dp[mask] = best cost when the first popcount(mask) people have been given exactly the jobs in mask. For paths, dp[mask][i] = best cost visiting the set mask and ending at i.
- 3Set the base case, such as dp[0] = 0 or dp[1 << start][start] = 0, and everything else to infinity.
- 4Transition by adding one unused item: for each state and each item j not in mask, update dp[mask | (1 << j)] from dp[mask].
- 5Process masks in increasing numeric order. Adding a bit always makes a larger number, so every state is final before it is used.
- 6Read the answer from the full mask (1 << n) - 1, plus any closing cost such as returning to the start city.
Worked example · Assigning 3 workers to 3 jobs at minimum cost
- cost[worker][job] = [[9, 2, 7], [6, 4, 3], [5, 8, 1]]. dp[mask] is the cheapest way to give the first k workers the jobs in mask, where k = number of set bits. dp[000] = 0.
- Worker 0 picks a job: dp[001] = 9 (job 0), dp[010] = 2 (job 1), dp[100] = 7 (job 2).
- Worker 1: dp[011] = min(dp[010] + 6, dp[001] + 4) = min(8, 13) = 8. dp[101] = min(dp[100] + 6, dp[001] + 3) = min(13, 12) = 12. dp[110] = min(dp[100] + 4, dp[010] + 3) = min(11, 5) = 5.
- Worker 2 takes the last free job: dp[111] = min(dp[110] + 5, dp[101] + 8, dp[011] + 1) = min(10, 20, 9) = 9.
- Answer 9: worker 0 does job 1 (2), worker 1 does job 0 (6), worker 2 does job 2 (1). Only 8 states were needed instead of listing all 3! = 6 orders, and the gap grows quickly: 20 workers is about 1 million states versus 2.4 x 10^18 orders.
Picture it
Planning a road trip through 12 cities, you do not need to remember the exact order you took so far, only which cities you have already seen and where you are now. Two different routes that visited the same cities and ended in the same place are equally good starting points for the rest of the trip, so you keep only the cheaper one.
Reference code
def tsp(dist):
# Held-Karp: shortest tour that starts and ends at city 0
n = len(dist)
INF = float("inf")
full = 1 << n
# dp[mask][i] = cheapest path from 0 visiting exactly mask, ending at i
dp = [[INF] * n for _ in range(full)]
dp[1][0] = 0
for mask in range(full):
if not mask & 1:
continue # every path starts at city 0
for last in range(n):
cost = dp[mask][last]
if cost == INF:
continue
for nxt in range(n):
if mask >> nxt & 1:
continue # already visited
new = mask | (1 << nxt)
dp[new][nxt] = min(dp[new][nxt], cost + dist[last][nxt])
return min(dp[full - 1][i] + dist[i][0] for i in range(1, n))
dist = [[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]]
print(tsp(dist)) # 80 (0 -> 1 -> 3 -> 2 -> 0)
dp[mask][last] keeps only the cheapest way to reach each (set, end) pair. Masks are processed in increasing order, so a state is complete before it is extended. The final line closes the tour back to city 0.
Key patterns
Travelling salesman (Held-Karp)
When: Visit every node exactly once with minimum total cost, n at most about 16 to 20
How: dp[mask][last]; transition to an unvisited next; answer is min over last of dp[full][last] + closing cost. O(n^2 * 2^n) time, O(n * 2^n) space.
Assignment
When: Match n people to n tasks with costs
How: dp[mask], where the next person to assign is popcount(mask). O(n * 2^n).
Shortest path visiting all nodes
When: Unweighted graph, must touch every node, may revisit
How: BFS over states (node, mask) starting from every node at once. O(n * 2^n) states.
Partition into groups
When: Split items into k equal-sum groups, or cover with fewest subsets
How: dp[mask] = progress after using mask (for example, current partial sum), or iterate submasks to choose the next group. O(n * 2^n) or O(3^n).
Real-world use
Small exact route planning
Field-service and delivery apps planning a single technician's day with 10 to 15 stops can run Held-Karp to get the provably shortest order in well under a second. For hundreds of stops, routing libraries such as Google OR-Tools switch to heuristics because 2^n becomes impossible.
Compiler and query optimisers
Database optimisers choose join order with dynamic programming over subsets of tables (the System R approach, also used in PostgreSQL's standard planner), and PostgreSQL switches to a genetic search (GEQO) once a query has 12 or more tables by default.
Game AI and puzzles
Puzzle and game solvers store which keys, coins or switches have been collected as a bitmask in the search state, so shortest-path searches like BFS over (position, mask) find the fastest way to collect everything.
Small team scheduling
Assigning a handful of on-call engineers or tasks with costs and constraints is the assignment problem; for small sizes dp[mask] is simple and exact (the Hungarian algorithm is the polynomial choice for larger ones).
In a project
A warehouse picking app guides a worker to collect 14 items for one order, and the walking distance between any two shelves is known. Today the app lists items in catalogue order, and workers walk far more than necessary.
- Build a 15 x 15 distance matrix: the packing station plus 14 shelves.
- Run Held-Karp with dp[mask][last]: 2^15 x 15, about 490,000 states and roughly 7 million transitions.
- Store a parent pointer for each state so the best order can be reconstructed and shown as a pick list.
- Fall back to a nearest-neighbour heuristic for orders above 18 items, where the exact DP becomes too slow or memory-heavy.
Impact: Each pick list is provably the shortest walk, computed in well under a second on the server. Shorter routes mean more orders picked per hour per worker, and the fallback keeps large orders responsive.
Trade-offs
Use it when
- n is at most about 20 and the state needs to remember which items are used
- Order matters only through the set used and maybe the last item
- You need an exact optimum, not a heuristic
Avoid it when
- n is larger than about 25; 2^n states no longer fit in time or memory
- A greedy or polynomial algorithm exists, such as the Hungarian algorithm for large assignment problems
- The full order history truly matters, not just the set
Cost: Held-Karp: O(n^2 * 2^n) time and O(n * 2^n) space. Assignment dp[mask]: O(n * 2^n) time, O(2^n) space. For n = 20, 2^20 is about 1 million.
Common mistakes
- Not recognising the small-n signal and trying brute-force permutations, which is O(n!).
- Defining dp[mask] without the last item when the cost depends on where you are, as in TSP.
- Processing states in the wrong order, so a state is used before all its inputs are final.
- Allocating dp[2^n][n] for n = 25 or more and running out of memory.
- Forgetting the closing edge back to the start in a tour, or adding it for a path that does not return.
Interview questions
Quick revision
- Signal: n <= 20 and you must remember which items are used.
- State: dp[mask] or dp[mask][last].
- Transition: add an unused item j, new mask = mask | (1 << j).
- Iterate masks in increasing order.
- TSP (Held-Karp): O(n^2 * 2^n) time, O(n * 2^n) space.
- Assignment: dp[mask], next person = popcount(mask), O(n * 2^n).
- 2^20 is about 1 million; 2^25 is about 33 million.
Check yourself
1. What is the time complexity of Held-Karp for the travelling salesman problem with n cities?
2. In the assignment DP dp[mask], which worker is assigned next?
3. Why can masks be processed in plain increasing numeric order?
4. A problem has n = 60 items. Is plain bitmask DP over all subsets practical?
Saved on this device. Create a free account to keep it on every device.
Practise this with Sam
A real mock interview, out loud, with an honest scorecard. Free to start.