Lessons from Bitmask DP

Four patterns you've seen:

$1.$ State compression: When tracking "which elements used," represent it as a bitmask. The state space becomes $O(2^n)$ subsets.

$2.$ Transitions via bit operations: Set bits, clear bits, check bits. These run in $O(1)$ and keep your code clean.

$3.$ Assignment problems: When matching $n$ items to $n$ slots in order, $dp[\text{mask}]$ alone suffices. Process items one by one.

$4.$ SOS DP: When you need sums over all subsets (or supersets), don't iterate submasks naively. Use the $O(n \cdot 2^n)$ technique. The constraint $n \leq 20$ is your signal. Anything larger and $2^n$ won't fit in time or memory.