What is Bitmask Dynamic Programming?
Learn bitmask DP — encoding subsets as integers to solve problems like TSP efficiently, with a Python code example.
Expected Interview Answer
Bitmask dynamic programming represents a subset of a small collection of items as a single integer, where bit i is 1 if item i is included, letting the DP state track “which items have been used so far” as an O(1) integer index instead of an explicit set, which is what makes problems like the traveling salesman problem solvable in O(2^n * n^2) instead of the naive O(n!).
The technique applies when n is small (typically up to about 20-22, since 2^n states must be enumerable) and the recurrence needs to know exactly which subset of elements has been processed, not just how many. Each state is a pair (mask, extra) where mask is the bitmask of used items and extra is any additional dimension like the current position; transitions try adding one new bit at a time using bitwise OR with a shifted 1, and checking membership is a bitwise AND. Classic applications include the traveling salesman problem, assigning n workers to n tasks optimally, counting Hamiltonian paths, and “can this set be partitioned into k groups satisfying a condition” problems. The tradeoff is exponential space and time in n, so bitmask DP is a tool for small n with a rich subset-dependent structure, not a general-purpose optimization.
- Encodes any subset of up to ~20 items as a single integer
- Bitwise operations (OR, AND, shift) make transitions O(1)
- Solves TSP-style problems in O(2^n * n^2) instead of O(n!)
- Naturally supports counting and existence queries over subsets
AI Mentor Explanation
A selector picking a batting order from 15 shortlisted players uses a checklist where each player has one box, and a specific lineup is represented by which boxes are ticked — that ticked pattern is exactly a bitmask. Instead of writing out every possible full lineup as a list of names, the selector can represent “these 6 players have already been picked” as one compact ticked pattern and quickly check if a new player is already ticked with a single glance at their box. Building up the squad one player at a time updates the pattern by ticking one more box, which mirrors setting one more bit. This compact tick pattern is what lets the selector reason about “which subset of players is committed so far” without ever writing out the full list each time.
Step-by-Step Explanation
Step 1
Confirm n is small enough
Bitmask DP needs 2^n states to be enumerable, so it is practical for roughly n <= 20-22.
Step 2
Define the mask as the state
Bit i of the mask is 1 if item i has been used/visited/selected so far; combine with any extra dimension like current position.
Step 3
Write transitions with bitwise ops
To add item i: check (mask >> i) & 1 == 0, then transition to mask | (1 << i).
Step 4
Iterate masks in increasing order
Process masks from 0 up to 2^n - 1 (or by popcount) so every transition reads an already-computed smaller mask.
What Interviewer Expects
- Explain why bitmask DP only works for small n (exponential state space)
- Show how bitwise OR/AND/shift implement subset membership and insertion
- Give a canonical example: traveling salesman problem or assignment problem
- State the resulting time complexity, e.g. O(2^n * n^2) for TSP
Common Mistakes
- Applying bitmask DP to n much larger than ~20, causing memory/time blowup
- Forgetting to also track the extra dimension (like current position) alongside the mask
- Iterating masks in the wrong order so a transition reads a not-yet-computed state
- Confusing bitmask DP with generic subset enumeration without memoizing shared states
Best Answer (HR Friendly)
“Bitmask dynamic programming is a trick for representing “which items have been used so far” as a single number instead of an explicit list, using one bit per item. It works great when the number of items is small, maybe up to 20, because then I can enumerate every possible subset as an integer and reuse work between subsets that share structure — the classic example is the traveling salesman problem.”
Code Example
def tsp(dist):
n = len(dist)
FULL = (1 << n) - 1
# dp[mask][i] = min cost to have visited cities in mask, ending at city i
dp = [[float("inf")] * n for _ in range(1 << n)]
dp[1][0] = 0 # start at city 0, only city 0 visited
for mask in range(1 << n):
for i in range(n):
if dp[mask][i] == float("inf") or not (mask & (1 << i)):
continue
for j in range(n):
if mask & (1 << j):
continue
new_mask = mask | (1 << j)
new_cost = dp[mask][i] + dist[i][j]
if new_cost < dp[new_mask][j]:
dp[new_mask][j] = new_cost
return min(dp[FULL][i] + dist[i][0] for i in range(n))Follow-up Questions
- Why does bitmask DP for TSP run in O(2^n * n^2) instead of O(n!)?
- How would you reconstruct the actual optimal tour, not just its cost?
- What is the practical n limit for bitmask DP and why?
- How would you adapt bitmask DP to count valid subsets instead of optimizing a cost?
MCQ Practice
1. What does bit i being 1 in a bitmask DP state typically represent?
In bitmask DP, each bit position corresponds to one item, and a set bit means that item is part of the current subset represented by the mask.
2. Why is bitmask DP typically limited to around n <= 20-22?
Since the state space size is 2^n, n around 20-22 already yields roughly a million to four million masks, which is close to the practical limit for time and memory.
3. What is the time complexity of the classic bitmask DP solution to the traveling salesman problem with n cities?
The DP has O(2^n * n) states (mask, last city) and each transition considers O(n) next cities, giving O(2^n * n^2) total time.
Flash Cards
What does a bitmask DP state represent? — A subset of items encoded as an integer, where bit i indicates whether item i is included.
How do you check if item i is in mask? — (mask >> i) & 1 == 1, or equivalently mask & (1 << i) != 0.
How do you add item i to mask? — new_mask = mask | (1 << i).
What is the practical n limit for bitmask DP? — Roughly n <= 20-22, since the state space grows as 2^n.