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 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: . Each bit is either not in mask, in mask but not in submask, or in both. Three choices per bit, so .