Superset DP

Superset — upward; dual SOS 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

• Loop direction — double count.
• Complement universe.
• 3-bit lattice.