SOS DP - Superset Version

Sometimes you need sum over supersets instead of subsets: Each mask, compute $\sum f[\text{supermask}]$ where supermask contains all bits of mask. This is the dual problem to what we just solved. The idea is symmetric.

Flip the update direction: instead of "if bit is set, add the version with bit off," do "if bit is off, add the version with bit on." pseudocode for i := 0 to n - 1 for mask := 0 to 2^n - 1 if (mask & (1 << i)) = 0 then dp[mask] := dp[mask] + dp[mask | (1 << i)]

Now $dp[\text{mask}]$ holds the sum over all supersets of mask. Same complexity: $O(n \cdot 2^n)$. This version is useful When want to aggregate over all masks that include a required set of bits.