1Understand
The idea
When n is at most about 20, represent "which items are used" as the bits of an integer. dp[mask] (or dp[mask][last]) is the best result using exactly that set. Transitions add one unused item with mask | (1 << i), for O(2ⁿ · n) or O(2ⁿ · n²) in total.
Intuition
When n is at most about 20, represent "which items are used" as bits of an integer. dp[mask] (or dp[mask][last]) is the best result using exactly that set of items.
Transitions add one unused item with mask | (1 << i). Iterate masks in order, or recurse with memo on the mask. Total states 2ⁿ or n·2ⁿ.
Bit tricks (mask & -mask, iterate submasks) show up in advanced variants.
What you will be able to do
- Encode sets as integers
- Add the last element to the state when needed
When to use it
- Visit every node once (small n)
- Assign n tasks to n workers
- n ≤ 16-20 with "all subsets"
2See it
Walkthrough
TSP-style mask DP
4 cities, mask bits = visited; start mask = 0001 (city 0).
1 / 4
dp[1<<0][0] = 0. Bit i set means city i is in the tour so far.
Live template
Line 1 active
Complexity: time O(2^n · n), space O(2^n)
O(n² · 2ⁿ) for TSP-like, O(n · 2ⁿ) for simpler masks. Impossible for n = 40; then need meet-in-the-middle or a different model. Space O(n · 2ⁿ) can be the limiter before time.
Read the walkthrough as text
TSP-style shortest path through all cities. n = 4 cities, start at 0.
dp[1 << 0][0] = 0, at city 0 with only 0 visited.- From each
(mask, u), try edgeu→vif bit v off: updatedp[mask|1<<v][v]. - Answer is min over
dp[(1<<n)-1][v] + dist[v][0]to return home. - 2⁴ · 4 states, each with ≤4 transitions.
Assignment problems use dp[mask] = min cost assigning bit-set workers to the next job.
3Recognise it
Kinds of problems (6)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Assignment problems
Example. Assign n workers to n jobs minimum cost.
How. dp[mask] = min cost covering mask; try add job j with worker popcount(mask).
Travelling salesman (mask + last node)
Example. Shortest tour visiting all cities once.
How. dp[mask][i] ending at i; transition from prev j by adding edge cost.
Partition into k subsets
Example. Split items into k groups with equal sum (small n).
How. Bitmask + target sum per group; backtrack or DP on masks.
Shortest path visiting all nodes
Example. Visit every node in small graph.
How. TSP / BFS on (node, mask) state space.
Mask over the letters still needed (stickers)
Example. Spell target using sticker subsets.
How. dp[mask] letters covered; try each sticker OR into mask.
Game states over used items (can I win)
Example. Turn game picking stones, win from mask.
How. dp[mask] winnable if any move leaves opponent losing state.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
Operator precedence
Why it happens. `&` and `<<` without parens looks fine on paper.
How it fails. mask & 1 << i == 0 parses as mask & (1 << i == 0), wrong branch logic.
Fix. Parenthesise: (mask & (1 << i)) == 0.
State too small
Why it happens. Mask alone encodes visited set for TSP transitions.
How it fails. TSP dp[mask] only, cannot know which city you are at to extend tour.
Fix. Add last-node dimension: dp[mask][i] ending at city i.
n too large
Why it happens. 2^n table is the textbook solution for subset DP.
How it fails. n=25 → 2^25 states, memory blow-up; need different algorithm.
Fix. Bitmask DP only when n ≤ ~20 (problem dependent).
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.