Sum Over Subsets (SOS DP): Yates’ Algorithm & High-Dimensional Prefix Sums in O(N 2^N)

A frequent subproblem in competitive programming asks: for every bitmask $M$, compute the sum of values $A[S]$ for all submasks $S subseteq M$. While iterating submasks directly takes $O(3^N)$, SOS DP reduces runtime to $O(N 2^N)$ via dimension-by-dimension prefix sums.

1. SOS DP Implementation Template

// C++20 SOS DP / Yates' Algorithm
void computeSOS(vector<int>& F, int N) {
    for (int i = 0; i < N; ++i) {
        for (int mask = 0; mask < (1 << N); ++mask) {
            if (mask & (1 << i)) {
                F[mask] += F[mask ^ (1 << i)];
            }
        }
    }
}