Bitmask DP & subset enumeration
Scenario
You have a classic Traveling Salesperson Problem (TSP) with N=18 cities. A naive permutations approach takes O(N!), which is 6.4 quadrillion operations and will definitely Time Limit Exceed (TLE).
How can you compress 18 true/false states into a single integer to solve this in milliseconds?
Why it exists
In graph theory and combinatorics, many problems (like TSP, Hamiltonian paths, and perfect matchings) are NP-hard and inherently require exploring permutations. Bitmask DP exists to change the complexity class entirely from factorial `O(N!)` to exponential `O(N^2 * 2^N)`, turning 'impossible' problems into solvable ones for small datasets.
Mental model
Think of an integer not as a number, but as an array of 32 boolean switches. If you have 10 items in a backpack, the number 5 (binary `00...00101`) means you took the 0th and 2nd items. This allows you to use simple integers as indices in a Dynamic Programming table.
Bitmask DP uses an integer's binary representation to represent a subset of items or a state of boolean variables. This technique drops the time complexity of factorial algorithms (like TSP) from `O(N!)` to `O(N^2 * 2^N)`, making them viable for N up to ~20.
Explanation
**1. The State Representation (The Bitmask):**
If we have `N` items, there are `2^N` possible subsets. Each subset maps directly to an integer from `0` to `2^N - 1`.
For example, if `N=3`, the integer 5 is `101` in binary. This perfectly represents a state where items 0 and 2 are 'included' (bits are set), and item 1 is 'excluded'.
*Reminder: Set a bit using `mask | (1 << v)` and check a bit using `mask & (1 << v)`.*
**2. Using Bitmasks as DP Indices:**
In classical DP, if you need to track which cities you've visited, you might try to pass an array or `vector<bool>` as state. However, arrays cannot be used as array indices for memoization! By using a bitmask, the state 'visited cities {0, 2, 4}' becomes the integer 21 (`10101`). You can now memoize the answer in `dp[21]`.
**3. The DP Transition:**
To build the DP solution, you transition from one state to the next by iterating through all items. If the item `v` is unvisited `(mask & (1 << v)) == 0`, you transition to the new state by setting the bit: `new_mask = mask | (1 << v)` and calculating the cost: `dist[u][v] + solve(v, new_mask)`.
**4. Subset Enumeration (Iterating over Submasks):**
Sometimes you need to iterate over every subset of a specific bitmask. A naive loop checks all numbers up to the mask, which is slow. Iterating through submasks directly takes `O(2^K)` per mask, where `K` is the number of set bits. When running this across all `2^N` possible masks, the total global complexity becomes exactly `O(3^N)`:
`for (int s = mask; ; s = (s - 1) & mask) { /* use s */; if (s == 0) break; }`
This cleverly subtracts 1 (flipping the lowest bits) and then `& mask` forces the result to strictly remain a subset of the original mask.
Code examples
Bitmask DP (Traveling Salesperson)
int n;
int dist[20][20];
int memo[20][1 << 20]; // memo[current_city][visited_mask]
int tsp(int u, int mask) {
// Base case: all n cities visited (mask is all 1s)
if (mask == (1 << n) - 1) return dist[u][0];
if (memo[u][mask] != -1) return memo[u][mask];
int ans = 1e9;
for (int v = 0; v < n; v++) {
// If city v is NOT visited (v-th bit is 0)
if ((mask & (1 << v)) == 0) {
// Recurse: move to v, turn on v-th bit in mask
int new_mask = mask | (1 << v);
ans = min(ans, dist[u][v] + tsp(v, new_mask));
}
}
return memo[u][mask] = ans;
}This reduces TSP from O(N!) down to O(N^2 * 2^N). For N=18, this runs in roughly 85 million operations, well under a 1-second time limit.
Key points
- Integers are boolean arrays: Use bits as true/false flags to compress state into a single dimension for O(1) DP lookups.
- Strictly for N <= 22: Bitmask DP is an exponential O(2^N) algorithm. Know the mathematical limits of the time complexity.
Common mistakes
- Using Bitmask DP for N > 25: Bitmask DP is powerful, but exponential. `2^25` is ~33 million. `2^30` is over 1 billion. If N is 30, a bitmask DP approach will cause a Memory Limit Exceeded (you cannot allocate `memo[1<<30]`) and a Time Limit Exceeded. Bitmask DP is strictly for very small N.
Recall questions
- What is the maximum practical value of N for which an `O(2^N)` Bitmask DP algorithm can run within a standard 1-second time limit?
- In a bitmask, what does the expression `mask | (1 << v)` accomplish?
- How can you iterate through all submasks (subsets) of a given `mask` efficiently?
Questions & answers
A developer writes a DP function `solve(int items[], vector<bool> visited)` to solve a knapsack variant. They try to use a `map<vector<bool>, int>` for memoization, but it is extremely slow. Why is this bad, and how does a bitmask fix it?
Using a `vector<bool>` as a map key involves hashing the entire vector or performing linear element-wise comparisons on every DP lookup, which adds a massive O(N) overhead. A bitmask compresses the boolean state into a single integer, allowing for O(1) array indexing (`memo[integer]`).
Approach: Understand the memory and lookup overhead of complex data structures in tight DP states.
In a TSP solver, a junior engineer checks if a city is visited using `if (mask ^ (1 << v))`. This introduces a severe bug. Why?
The XOR operator `^` flips the bit. If the bit was 1, it becomes 0. If it was 0, it becomes 1. It does not *check* the bit. To check if a bit is visited, they must use the AND operator: `if (mask & (1 << v))`.
Approach: Distinguish between bitwise toggling (XOR) and bitwise masking/checking (AND).
Continue learning
Previous: Bit manipulation tricks for CP