Bitmask DP
You've handled linear, 2D, and tree states. Bitmask DP tracks which elements you've used in a subset.
Lessons
1. Intro
The Goal
2. Vocabulary - Bitmask
Subset as integer
3. Bit Operations
The tools you need
4. Simple Example - Subset Membership
Concrete usage
5. Iterating Subsets
Enumeration patterns
6. Quiz: Bit Operations
Knowledge check
7. The Bitmask DP Pattern
Dp[mask] indexed by subsets
8. When Bitmask DP?
Recognition tips
9. Quiz: When Bitmask DP
Knowledge check
10. Subset Sum - Problem Statement
Entry problem
11. Subset Sum - Key Observation
Bitmask as subset
12. Subset Sum - Implementation
The code
13. Quiz: Subset Sum
Knowledge check
14. LeetCode 1879 Minimum XOR Sum of Two Arrays - Problem Statement
LeetCode 1879
15. Assignment - key observation
Process in order
16. Assignment - State Design
Dp[mask] alone
17. Assignment - Implementation
O(n × 2^n)
18. Quiz: Assignment
Knowledge check
19. Hamiltonian Flights - Problem Statement
Count routes, bitmask DP
20. TSP - key observation
Visited set + current city
21. TSP - State Design
Dp[mask][last]
22. TSP - Transition
Add next city
23. TSP - Implementation
O(n² × 2^n)
24. Quiz: TSP
Knowledge check
25. LeetCode 698 Partition to K Equal Sum Subsets - Problem Statement
LeetCode 698
26. K Subsets - key observation
Track partial sum
27. K Subsets - Implementation
The code
28. Why Sum Over Subsets?
A new problem type
29. Iterating Submasks
The O(3^n) way
30. SOS DP - The Core Idea
Build subsets bit by bit
31. SOS DP - Transition
Include or exclude bit i
32. Quiz: SOS DP Transition
Knowledge check
33. SOS DP - Space Optimization
Drop the second dimension
34. SOS DP - Implementation
The code
35. Bit Problem - Problem Statement
CSES 1654
36. Bit Problem - Query Analysis
Subset relationships
37. Bit Problem - Implementation
Three SOS passes
38. SOS DP - Superset Version
The dual problem
39. Quiz: SOS DP Applications
Knowledge check
40. When to Use SOS DP
Recognition and practice
41. Lessons from Bitmask DP
summary
42. Section Recap
What we learned
Practice Problems
Classic TSP variant using BFS with bitmask
Combines probability with bitmask DP elegantly
Covered with full walkthrough in this section.
Covered with full walkthrough in this section.
Covered with full walkthrough in this section.
Covered with full walkthrough in this section.
Covered with full walkthrough in this section.
Covered with full walkthrough in this section.
Covered with full walkthrough in this section.
Classic bitmask DP with primes. Track which primes are used to ensure coprimality.
Choose k dishes with satisfaction bonuses. TSP variant with subset selection.
Find minimum subset with GCD 1. Inclusion-exclusion with bitmask over prime factors.
Find pair with AND = 0. SOS DP to propagate answers through submasks.
Maximize a[i] OR (a[j] AND a[k]). SOS DP tracking two rightmost indices per mask.
Remove minimum chars to avoid x-prime substrings. Aho-Corasick + bitmask DP.
Partition tasks into sessions. Bitmask DP tracking remaining time per session.
Assign hats to people uniquely. Bitmask over people, iterate over hats.
Connect all points in both groups. Bitmask DP over second group connections.
TSP on strings - minimize total length. Classic bitmask DP with path reconstruction.
Count perfect matchings using bitmask DP - classic application of subset enumeration.
Partition into groups maximizing total score - subset DP iterating over all submasks.
Count permutations satisfying < or > constraints - teaches insertion DP pattern.