Superset DP — Sum Over Supersets

Flip inclusion direction: update masks from submasks upward to accumulate over supersets—dual SOS loop order.

Try this in Python

n = 3
g = [1] * (1 << n)
for i in range(n):
    for mask in range((1 << n) - 1, -1, -1):
        if ((mask >> i) & 1) == 0:
            g[mask] += g[mask | (1 << i)]
print(g)

Key takeaways

• Careful loop directions prevent double counting.
• Often appears after complementing the universe.
• Draw 3-bit lattice once.