Iterating Submasks

Before SOS DP, let me show you the naive submask iteration. For a given mask, you can enumerate all its submasks with this trick:

for submask := mask; submask > 0; submask := (submask - 1) & mask // process submask
// don't forget submask = 0

This generates all submasks in decreasing order. Why does it work? Subtracting $1$ flips the lowest set bit and sets all lower bits. The AND with mask keeps only bits that were in the original mask.

Total work across all masks: $\sum_{\text{mask}} 2^{\text{popcount(mask)}} = 3^n$. Each bit is either not in mask, in mask but not in submask, or in both. Three choices per bit, so $3^n$.