What Bitmask DP Solves

Bitmask DP solves problems where you need to track which elements from a small set ($n \le 20$) have been selected. Classic examples include TSP, assignment problems, and counting valid arrangements.

This works because an integer with $n$ bits can represent any subset of $n$ elements. Bit $i$ being $1$ means element $i$ is included. This gives $2^n$ possible states, which is manageable for small $n$.