Neel Mishra
← All Posts
DSA · Bit Manipulation· Part 20 of 32

SOS DP and Zeta/Mobius Transforms

May 2026 · 30 min read

SOS DP means "sum over subsets." It turns many O(3^n) mask/submask loops into O(n * 2^n) transforms. If you need "for every mask, combine values over all submasks", SOS DP is usually the first optimization to consider.

Sum Over Subsets

Given f[mask], compute:

g[mask] = sum of f[sub] over all submasks sub of mask

Naively this is O(3^n). The zeta transform does it in O(n * 2^n):

vector<long long> g = f;
for (int bit = 0; bit < n; ++bit) {
    for (int mask = 0; mask < (1 << n); ++mask) {
        if (mask & (1 << bit)) {
            g[mask] += g[mask ^ (1 << bit)];
        }
    }
}

Sum Over Supersets

For each mask, sum over all supermasks that contain it:

vector<long long> g = f;
for (int bit = 0; bit < n; ++bit) {
    for (int mask = 0; mask < (1 << n); ++mask) {
        if ((mask & (1 << bit)) == 0) {
            g[mask] += g[mask | (1 << bit)];
        }
    }
}

Mobius Inversion

If zeta transform adds from submasks, Mobius inversion reverses it by subtracting.

// Invert subset zeta transform.
for (int bit = 0; bit < n; ++bit) {
    for (int mask = 0; mask < (1 << n); ++mask) {
        if (mask & (1 << bit)) {
            g[mask] -= g[mask ^ (1 << bit)];
        }
    }
}

OR Transform

OR convolution asks for pairs where a | b = mask. The OR zeta transform is the same as subset zeta: values flow from smaller submasks to larger masks.

void or_zeta(vector<long long>& a, int n) {
    for (int bit = 0; bit < n; ++bit)
        for (int mask = 0; mask < (1 << n); ++mask)
            if (mask & (1 << bit))
                a[mask] += a[mask ^ (1 << bit)];
}

AND Transform

AND convolution flows from supermasks down to submasks.

void and_zeta(vector<long long>& a, int n) {
    for (int bit = 0; bit < n; ++bit)
        for (int mask = 0; mask < (1 << n); ++mask)
            if ((mask & (1 << bit)) == 0)
                a[mask] += a[mask | (1 << bit)];
}

Recognition Guide

Practice Problems