SOS DP (Sum over Subsets)

Compute, for every mask, the sum over all of its submasks:

$F(S)={\sum }_{T\subseteq S}f(T)$

in $O(2^{n}n)$ instead of the naive $O(3^n)$.

The algorithm

// subset sum: F[S] = sum of f[T] over T subset of S
vector<long long> F(f);
for (int i = 0; i < n; i++)
    for (int mask = 0; mask < (1 << n); mask++)
        if (mask >> i & 1)
            F[mask] += F[mask ^ (1 << i)];

Three lines. The outer loop over bit positions is essential — swapping the loops gives a different (wrong) transform.

Why it works

Process bits one at a time. After stage $i$, $F[\text{mask}]$ holds the sum over all $T$ that agree with mask on bits $>i$ and are arbitrary submasks on bits $\le i$. Stage $i+1$ merges the two halves. After $n$ stages, $F$ is the full subset sum.

Formally, this is the zeta transform of the subset lattice, computed by a dimension-by-dimension sweep — exactly the same structure as a multidimensional prefix sum, with each dimension having size 2.

The four directions

// subset sum (zeta)
for (int i = 0; i < n; i++) for (int m = 0; m < (1<<n); m++)
    if (m >> i & 1) F[m] += F[m ^ (1<<i)];
 
// subset sum INVERSE (Möbius)
for (int i = 0; i < n; i++) for (int m = 0; m < (1<<n); m++)
    if (m >> i & 1) F[m] -= F[m ^ (1<<i)];
 
// superset sum
for (int i = 0; i < n; i++) for (int m = 0; m < (1<<n); m++)
    if (!(m >> i & 1)) F[m] += F[m | (1<<i)];
 
// superset sum inverse
for (int i = 0; i < n; i++) for (int m = 0; m < (1<<n); m++)
    if (!(m >> i & 1)) F[m] -= F[m | (1<<i)];

OR and AND convolution

$h(S)={\sum }_{A\cup B=S}f(A)g(B)$

1. Zeta-transform $f$ and $g$ (subset sums).
2. Multiply pointwise.
3. Möbius-transform the result.

$O(2^{n}n)$. Replace subset with superset to get AND-convolution. For XOR-convolution use FWHT — same shape, different transform.

Convolution	Transform
OR ($A\cup B=S$)	subset-sum zeta / Möbius
AND ($A\cap B=S$)	superset-sum zeta / Möbius
XOR ($A\oplus B=S$)	Walsh-Hadamard
Disjoint union ($A\cup B=S$, $A\cap B=\varnothing$)	subset convolution — see below

Subset convolution — $O(2^n{n}^2)$

$h(S)={\sum }_{\begin{array}{c}A\cup B=S\\ A\cap B=\varnothing \end{array}}f(A)g(B).$

OR-convolution over-counts because it allows overlaps. The fix is to rank by popcount: define ${\hat{f}}_k(S)=f(S)$ if $|S|=k$, else 0. Then

${\hat{h}}_k={\sum }_{i+j=k}{\hat{f}}_i\ast {\hat{g}}_j$

using OR-convolution, and $h(S)={\hat{h}}_{|S|}(S)$. The popcount rank makes disjointness automatic, because $|A|+|B|=|S|$ only when they are disjoint.

$O(2^n{n}^2)$ — practical to $n\approx 20$, and the standard tool for “partition a set into two parts” counting problems.

Applications

Problem	Method
For each mask, sum over its submasks	direct SOS
For each mask, count array elements that are submasks of it	SOS over a frequency array
Maximum $f(A)+f(B)$ with $A\cap B=\varnothing$	SOS storing the best two values
Count pairs with $a_i\&a_j=0$	superset SOS on the complement
Count pairs with $a_i\mid a_j=$ full	subset SOS
Number of ways to cover a set with disjoint pieces	subset convolution
Steiner tree merge step	$3^k$ → subset convolution
Inclusion-exclusion over $n$ constraints	Möbius transform

The “maximum over submasks” variant

Store the best two values with distinct masks so you can combine them without overlap:

// dp[mask] = best value among submasks of mask
for (int i = 0; i < n; i++)
    for (int m = 0; m < (1<<n); m++)
        if (m >> i & 1) dp[m] = max(dp[m], dp[m ^ (1<<i)]);

Then “maximum $f(A)+g(B)$ with $A\cap B=\varnothing$” is ${\max }_m(d{p}_f[m]+d{p}_g[\overline{m}])$.

Memory

$2^n$ values. For $n=20$ and long long that is 8 MB — fine. For $n=24$ it is 134 MB — use int or process in halves.

See also: Enumerating Submasks · FWHT · Bitmask DP