Section Recap

You learned Bitmask DP for subset-based states.

$1.$ A bitmask represents a subset as an integer. Bit $i$ set means element $i$ is included. This compresses exponential state spaces into manageable $O(2^n)$.

$2.$ TSP (Traveling Salesman Problem)-style problems need $dp[\text{mask}][\text{last}]$: which cities visited, which city you're at. Assignment problems often need just $dp[\text{mask}]$.

$3.$ SOS DP handles subset aggregation in $O(n \cdot 2^n)$. Process one bit at a time, building from smaller flexibility to full subset sums.

When $n \leq 20$ and track subsets, think bitmask. The exponential state space is tractable for small $n$.