CONCEPT · International Grandmaster
Bitmask DP
also SOS · subset DP · Held-Karp
n ≤ 20: the used set is an integer. 2^n states, often times n. Iterate masks so subsets finish first.
Intuition
The subset is the missing dimension you used to put in the array index. Bits are that index.
When to reach for it
- TSP / Hamiltonian path
- Assignment / counting matchings
- CSES Elevator Rides, Hamiltonian Flights
- Meet-in-the-middle at n≈30
Usual pits
- n=24 tables MLE
- i not in mask
- Loop order that reuses an item (0/1 vs unbounded again)
- n=30 without splitting the set