Bitmask DP (State Compression)
Use bits to represent subset states, enabling DP over all subsets efficiently. Essential for Travelling Salesman, subset selection, and assignment problems.
Bitmask DP (State Compression)
Use bits to represent subset states, enabling DP over all subsets efficiently. Essential for Travelling Salesman, subset selection, and assignment problems.
TSP on 4 cities. State: dp[mask][city] = min cost visiting cities in 'mask', ending at 'city'. Start: dp[0001][0]=0.
Subsets as integers
Sort each bitmask expression by what it does to the subset.
Tap a piece, then tap where it goes — or drag it. Tap the tray to take one back.
Test membership
Drop items hereAdd an element
Drop items hereRemove an element
Drop items hereTest your knowledge
How do you iterate over all subsets of a bitmask m?
The short version
Imagine tracking which cities a salesman has visited using light switches. Each switch ON/OFF represents visited/not visited. Instead of storing lists, you store a single number whose binary bits encode the entire state.
In more depth
Subsets as Numbers
A bitmask of n bits can represent all 2^n subsets of n elements.
Common Operations:
mask & (1 << i)mask | (1 << i)mask & ~(1 << i)for (s = m; s > 0; s = (s-1) & m)TSP Pattern:
dp[mask][i] = min cost to visit cities in 'mask' ending at city i
Key Gotchas:
When to reach for this
- Visit all nodes exactly once (TSP/Hamiltonian Path)
- Select k items from n with complex constraints
- n is small (≤ 20) and need to consider all subsets
- Keywords: 'all possible subsets', 'assignment problem'
Interview Questions
Love this visualization?
Sign up to track your progress, earn achievements, use the AI assistant, and access your personal learning dashboard.
100% free • No credit card required