Bitmask Dynamic Programming for Coding Interviews: Subsets, Assignments and the Traveling Salesman
2 views
Bitmask DP looks intimidating, but it is one of the most predictable patterns in harder coding interviews. The signal is almost always the same: a small n (usually 20 or fewer), and a problem where the state depends on which items have been used, not the order they were used in. When you see n <= 16 or n <= 20 in the constraints, consider bitmasks.
The basic idea
Represent a set of used items as an integer whose i-th bit is 1 if item i has been used. With n items there are 2^n masks, which is about one million for n = 20. Useful operations:
- Check whether item i is used: mask & (1 << i)
- Add item i: mask | (1 << i)
- Remove item i: mask & ~(1 << i)
- Count used items: bin(mask).count("1")
- Iterate over submasks of mask: sub = mask; while sub: ...; sub = (sub - 1) & mask
Pattern 1: assignment problems
"Assign n workers to n jobs to minimize total cost." Let dp[mask] be the minimum cost of assigning the first popcount(mask) workers to the jobs in mask. The next worker index is implied by the number of bits set, which keeps the state one-dimensional:
def min_cost(cost):
n = len(cost)
INF = float("inf")
dp = [INF] * (1 << n)
dp[0] = 0
for mask in range(1 << n):
w = bin(mask).count("1")
if w >= n or dp[mask] == INF:
continue
for j in range(n):
if not mask & (1 << j):
nxt = mask | (1 << j)
dp[nxt] = min(dp[nxt], dp[mask] + cost[w][j])
return dp[(1 << n) - 1]
That's O(n * 2^n), which is fine for n up to about 20. LeetCode 1879 (Minimum XOR Sum of Two Arrays) and 1947 (Maximum Compatibility Score Sum) use exactly this template.
Pattern 2: the traveling salesman
For TSP you also need to know where you currently are, so the state becomes dp[mask][last]: the shortest path that visits exactly the cities in mask and ends at city last. Transition by going to an unvisited city. Complexity is O(n^2 * 2^n). LeetCode 847 (Shortest Path Visiting All Nodes) is a BFS variant of the same idea, with (node, mask) as the BFS state, and 943 (Find the Shortest Superstring) is TSP over string overlaps.
Pattern 3: partitioning into groups
"Can you split the array into k subsets with equal sums?" (LeetCode 698). A neat bitmask solution stores dp[mask] = the running sum modulo the target for the elements in mask, which is valid if you only add an element when it doesn't overflow the current bucket. Problems like 1986 (Minimum Number of Work Sessions) also use submask enumeration, which costs O(3^n) in total. That's a good fact to mention, because interviewers like hearing why it is 3^n and not 4^n.
How to present it in an interview
1. Point to the constraint: "n is at most 16, so 2^n states is feasible."
2. Define the state in one sentence, including what is implied (like the worker index from popcount).
3. Give the transition and the complexity before coding.
4. Mention bit tricks clearly; name your variables so the interviewer can follow.
Bitmask problems are where nerves cause the most off-by-one and precedence bugs (remember to parenthesize mask & (1 << i)). Practice explaining the state out loud until it feels routine. Some candidates also use Linkjob AI (https://linkjob.ai) for real-time help during live technical interviews when they need to keep their reasoning on track. Once the pattern is familiar, these "hard" problems become some of the most mechanical ones on the list.