Sometimes you need sum over supersets instead of subsets: Each mask, compute 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." plaintext 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 holds the sum over all supersets of mask. Same complexity: . This version is useful When want to aggregate over all masks that include a required set of bits.