Bitmask DP
Dynamic Programming with Bitmasking allows solving problems involving subsets or assignments where N is small (up to 20).
Graph Visualization
DP Table (Min Cost)
| Mask | City 0 | City 1 | City 2 | City 3 |
|---|
Ready to start
Cities:
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Intuition
The Restriction: Standard DP arrays work well when states are indices (e.g., dp[i]). But what if the state is a set of visited cities or available jobs?
The Solution: Use an integer as a bitmask to represent a set. If the j-th bit is set (1), element j is present/visited.
Since an integer can store up to 30-60 bits, we can represent any subset of size N efficiently if N <= 20.
Concept
Bit Operations Recap:
- Set bit i:
mask | (1 << i) - Check bit i:
(mask >> i) & 1 - Toggle bit i:
mask ^ (1 << i) - All bits set:
(1 << N) - 1
State Definition: Usually dp[mask][current_element], where mask represents the set of visited elements and current_element is the last added item.
How it Works
- Definite State: Identify what needs to be tracked. Usually "what elements are used" (mask) and "where are we now" (index).
- Transitions: Iterate through all subsets (masks) and try adding an available element (unvisited bit).
- Base Cases: `dp[0][...]` or `dp[1 << start_node][start_node]` usually initialized to 0 or cost.
Step-by-Step Breakdown
1. Initialize: Create a DP table of size `2^N * N`. Fill with infinity or appropriate default.
2. Base Case: Set starting masks (e.g., visiting the first city).
3. Iterate: Loop through `mask` from 1 to `2^N - 1`.
4. Inner Loop: Loop through `u` (current node) and `v` (next node).
5. Update: If `u` is in `mask` and `v` not in `mask`, update `dp[mask | (1<
When to Use
- Problems involving permutations or subsets where N is small (N <= 20).
- Traveling Salesman Problem (TSP).
- Assignment Problems (Assign N jobs to N people).
- Hamiltonian Path/Cycle problems.
When NOT to Use
- When N > 20 (Space/Time 2^N becomes too large).
- When the problem can be solved greedily or using standard flow algorithms.
How to Identify
"Find shortest path visiting all nodes", "Assign N tasks to N workers with min cost", Constraints: N <= 20.
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.