Чем перебор подмасок (for sub = mask; ...) отличается по сложности от SOS DP — почему 3^n?

Идиома sub = (sub - 1) & mask корректно перебирает все непустые подмаски mask по убыванию. Для одной маски с k установленными битами она делает $2^k$ итераций.

Суммарно по всем маскам: $\sum_{mask} 2^{popcount(mask)}$. Считаем комбинаторно — сколько масок имеет ровно k битов? $\binom{n}{k}$. Тогда:

(по биному Ньютона). Поэтому полный перебор всех подмасок всех масок — это $O(3^n)$, а не $4^n$.

Интуиция «$3^n$»: каждый бит независимо находится в одном из трёх состояний — «не в маске», «в маске и в подмаске», «в маске, но не в подмаске». Три варианта на бит → $3^n$.

for (int mask = 0; mask < (1 << n); ++mask)
  for (int sub = mask; ; sub = (sub - 1) & mask) {
    // обработка подмаски sub
    if (sub == 0) break;   // важно: 0 обрабатываем и выходим
  }

Для $n=20$: $3^{20} \approx 3.5 \cdot 10^9$ — на грани TLE. Если задача сводится к сумме по подмаскам, SOS DP за $O(n\cdot 2^n)$ почти всегда лучше ($2\cdot10^7$ против $3.5\cdot10^9$).