Why Sum Over Subsets?

You've learned to use bitmasks as DP states. Now here's a different problem: given values $f[0], f[1], \ldots, f[2^n - 1]$, compute for each mask the sum of $f[\text{submask}]$ over all submasks of that mask. Example: if $n = 2$ and mask $= 3$ (binary $11$), its submasks are $\{0, 1, 2, 3\}$ (binary $00, 01, 10, 11$).

You need the sum $f[0] + f[1] + f[2] + f[3]$. The naive approach iterates all submasks for each mask. That's $O(3^n)$. With $n = 20$, that's $3.5$ billion operations. Too slow. SOS DP does it in $O(n \cdot 2^n)$, about $20$ million operations for $n = 20$.