SOS DP - The Core Idea

Instead of iterating subsets directly, build them incrementally. Process one bit position at a time. For each bit, either keep it or turn it off (if it was on).

Define $dp[\text{mask}][i]$ = sum of $f[\text{submask}]$ where submask matches mask in bits $i+1$ through $n-1$, and can differ in bits $0$ through $i$. Base case: $dp[\text{mask}][-1] = f[\text{mask}]$. No bits are flexible yet, so the only "submask" is mask itself. Final answer: $dp[\text{mask}][n-1]$ gives the sum over all submasks.