Lesson 286
Bitmask DP
Subsets as Integers · Held-Karp
1:00How to represent subsets as integers and run dynamic programming over all 2^n subsets to solve problems like finding Hamiltonian paths in O(2^n · n²) time.
By the end, you can
- Convert a subset of n items to its integer mask by setting the appropriate bits.
- Decode an integer mask back to the set of items it represents.
- Write the TEST, SET, and CLEAR expressions for a single item in a mask.
- Explain the structure of the bitmask DP table and why masks must be swept in increasing order.
- Trace the Held–Karp recurrence on a small graph to fill the DP table and count Hamiltonian paths.
- State the O(2ⁿ · n²) complexity of bitmask DP and identify the practical upper bound on n.
Up next in String Algorithms, Advanced DP & Competitive Techniques
