When to Use SOS DP

Use SOS DP when you see these patterns:

$1.$ "For each subset, aggregate over all its subsets (or supersets)." Direct SOS application.

$2.$ "Count pairs where one bitmask is a subset of another." Precompute subset sums, then query.

$3.$ "Find if there exists a subset with property X contained in mask." Store boolean flags, SOS computes OR. The constraint $n \leq 20$ (or values up to $2^{20}$) signals bitmask techniques. If the problem involves subset/superset relationships, think SOS.