Bitmask DP
Overview
A Dynamic Programming technique that uses integers to represent subsets of items, enabling fast array indexing for state memoization.
It transforms a problem that looks like O(N!) (like permutations of N items) into O(2^N * N^2). It's only viable when N is very small (usually N <= 20).
Where used: Traveling Salesperson Problem, Assignment Problem (bipartite matching)
Why it exists
Problem: In some DP problems (like Traveling Salesperson), the 'state' you need to track is the exact set of items/cities you have visited so far. Tracking a `Set` or `List` in DP memoization is incredibly slow and takes too much memory.
Naive approach: Use a `Set<Integer>` as part of your memoization key.
Better idea: Represent the set of visited items as a single integer by treating its bits as boolean flags. For N items, a single integer from 0 to 2^N - 1 perfectly encodes every possible subset. This allows O(1) state transitions and array-based memoization.
Why learn this
- It is the standard solution for NP-hard problems where N is suspiciously small (10-20) in competitive programming.
Mental model
You have a dashboard with 10 light switches. Instead of writing down 'Switches 1, 3, and 4 are ON', you just read the binary number `0000001101` and call it state 13.
Bitmask DP compresses a boolean array of length N into a single integer. The DP state usually looks like `dp(mask, last_visited)`. To mark the i-th item as visited, we use bitwise OR: `mask | (1 << i)`. To check if the i-th item is visited, we use bitwise AND: `mask & (1 << i)`.
Repeated decision: Which unvisited item (where the i-th bit in the mask is 0) should I visit next to minimize/maximize the score?
Deep dive
When you see constraints like `1 <= N <= 15`, it's a massive hint. An `O(N^2)` or `O(N^3)` algorithm is too fast for N=15, and an `O(N!)` backtracking algorithm is too slow (`15! > 10^12`). The sweet spot is `O(2^N)`, which points directly to Bitmask DP.
A bitmask is just an integer. If we have 4 items, the integer `5` in binary is `0101`. This means the 0th item and the 2nd item have been selected.
In the famous Traveling Salesperson Problem, you need to visit all cities with minimum cost. The DP state is `(mask, last_city)`.
`mask` tells us which cities we've visited so far.
`last_city` tells us where we are right now, so we know how much it costs to travel to the next city.
From state `(mask, u)`, we loop over all cities `v`. If the `v`-th bit in `mask` is `0` (meaning `v` is unvisited), we can travel to `v`. The cost is `dist[u][v] + dp(mask | (1 << v), v)`. We take the minimum over all valid `v`. By memoizing this, we avoid recalculating paths for the same subset of cities, cutting the time from `O(N!)` down to `O(2^N * N^2)`.
Key points
- Complexity: Time is usually O(2^N * N) or O(2^N * N^2). Space is O(2^N * N) for the memoization table. N must be small (N <= 20).
- Bitwise Operations: Check if i-th bit is set: `mask & (1 << i) != 0`. Set the i-th bit: `mask | (1 << i)`. Toggle the i-th bit: `mask ^ (1 << i)`.
Pattern: Bitmask DP
Recognition cues:
- Find permutations/subsets
- Constraint N <= 20
- Problem is NP-Hard but constraints are suspiciously small
Failure signals
- The constraints say N can be up to 1000. (Bitmasking is impossible; look for greedy or standard DP).
Engineering examples
Delivery Routing
Finding the optimal route for a delivery truck with 12 stops.
12 stops is small enough for the Traveling Salesperson Problem to be solved exactly using Bitmask DP in milliseconds.
When not to use
- When N > 20: The memory for `2^21` integers starts exceeding standard competitive programming limits, and time complexity balloons.
Common mistakes
- Operator precedence bugs: Bitwise operators like `&` and `|` have lower precedence than equality `==` in many languages. Always wrap bitwise checks in parentheses: `if ((mask & (1 << i)) != 0)`.
- Applying it when N is too large: If N is 30, `2^30` is a billion. An array of size 1 billion will cause a Memory Limit Exceeded error. Bitmask DP is strictly for small N.
Recall questions
- What is the maximum typical value for N in a Bitmask DP problem?
- How do you check if the `i`-th item is already in the bitmask?
Understanding checks
If your mask is `10` (binary `1010`) and you visit city 0, what is your new mask?
11 (binary `1011`).
City 0 corresponds to the 0th bit (the 1s place). `1010 | 0001` becomes `1011`, which is 11 in decimal.
A developer checks if an item is unvisited using `if mask & (1 << i) == 0:`. In Python this works, but in C++ it might fail. Why?
Operator precedence. In C++, `==` evaluates before `&`.
It evaluates as `mask & ((1 << i) == 0)`. Since `1 << i` is never 0, it becomes `mask & 0`, which is always 0.
Questions & answers
Shortest Path Visiting All Nodes
Use BFS, but instead of marking nodes as visited, mark `(node, mask)` states as visited.
Approach: When the mask reaches `(1 << N) - 1`, you have visited all nodes.
Practice tasks
Matchsticks to Square
You are given an integer array matchsticks. You want to use all the matchsticks to make one square. Return true if you can make this square and false otherwise. (Hint: N <= 15).
Continue learning
Previous: Bitwise operators
Previous: State & transition