On this page

SOS DP (Sum over Subsets)

You have a value A[mask] for every bitmask of bits. For every mask you want

the sum of A over all submasks. Done naively, mask by mask, this costs steps — for , about 3.5 billion. SOS DP (Sum over Subsets DP) computes all answers in steps — about 21 million for — with a triple loop of three lines. The same three lines, with + turned into -, undo the transform; with the bit test flipped, they compute sums over supersets instead.

Why should you care? Because a surprising number of counting problems about bitwise operations collapse into "sum over submasks": how many pairs have a & b == 0? How many pairs have a | b == x? How many groups of numbers have AND equal to zero? For each number, is there another with no common bit? Each of these is one SOS pass plus a little arithmetic.

This lesson assumes Bitmask DP (masks as sets, submask enumeration and its cost) and Prefix Sums (2-D prefix sums in particular).

Why this exists

Submask enumeration (s = (s - 1) & mask) visits each pair (submask, mask) once, which is pairs. That is already much better than the of "test every pair of masks". But when the inner work is just adding — no choice, no max over groups — is wasteful: the sums for different masks share almost all their terms. F[1111] and F[1110] overlap in eight of their sixteen terms, and SOS DP shares that work systematically.

The technique has several independent histories. In combinatorics, the transform is the zeta transform on the lattice of subsets, and its inverse is the Möbius transform; Gian-Carlo Rota's 1964 paper "On the foundations of combinatorial theory I: Theory of Möbius functions" made both central to enumerative combinatorics. Frank Yates' 1937 method for analysing factorial experiments used the same dimension-by-dimension butterfly. In exact algorithms, Kennes (1992) gave the fast Möbius transform for Dempster–Shafer belief functions, and Björklund, Husfeldt and Koivisto (2006–2009) used it to compute the chromatic number of a graph in . Competitive programmers learned it as "SOS DP", popularised by a 2016 Codeforces tutorial by user usaxena95 ("SOS Dynamic Programming [Tutorial]").

Pattern triggers

If the problem says or has…Think of…
"for every mask, the sum / count / max over all its submasks"SOS DP (subset zeta),
"… over all supersets"Superset SOS (flip the bit test)
"number of with a[i] & a[j] == 0"Count array + SOS, query the complement of a[i]
"number of with a[i] | a[j] == a[i]" ( is a submask of )Subset SOS of counts
"number of pairs with a | b == x", for every OR convolution: SOS, square pointwise, inverse SOS
"number of pairs/triples with AND exactly "Superset SOS, power pointwise, inverse superset SOS
"count subsets whose AND is 0" / "whose OR is full"Superset (or subset) counts + inclusion–exclusion over masks
"exactly" a mask from "at most" / "at least" countsMöbius transform (inverse SOS) = inclusion–exclusion
values up to or and bitwise conditionsValues are masks of 20–22 bits: arrays of size –
"XOR of the pair equals "Not SOS: Walsh–Hadamard transform (see Variations)
"split into groups, maximise", needs to choose a submaskSubmask enumeration , not SOS (Bitmask DP)

The meta-trigger: a bitwise condition between two elements that can be rewritten as "one mask is contained in another". a & b == 0 means . a | b == a means . a & b == a means . Containment is exactly what SOS sums over.

Intuition & first principles

What a "submask" is, again

A mask is a set of bit positions. sub is a submask of mask (written ) when every 1-bit of sub is also a 1-bit of mask; in code, (sub & mask) == sub. The mask 101 has four submasks: 000, 001, 100, 101. A mask with one-bits has submasks.

A tiny example

Take and A = [3, 1, 4, 1, 5, 9, 2, 6] (so A[000] = 3, A[001] = 1, A[010] = 4, …, A[111] = 6). Then

  • F[000] = A[000] = 3.
  • F[101] = A[000] + A[001] + A[100] + A[101] = 3 + 1 + 5 + 9 = 18.
  • F[111] = everything = 31.

Doing this for all 8 masks by enumerating submasks touches (submask, mask) pairs. SOS DP will do it with additions.

The key idea: a submask is a point below you in a cube

Write a 3-bit mask as a point with each coordinate 0 or 1: the corners of a cube. sub ⊆ mask means every coordinate of sub is the matching coordinate of mask. So F[mask] is the sum of A over the box of points below mask in every coordinate — an -dimensional prefix sum on a grid of side 2.

You already know how to do 2-D prefix sums one dimension at a time: first take prefix sums along every row, then along every column of the result (Prefix Sums). After the row pass, cell holds the sum of row up to ; after the column pass it holds the full rectangle. SOS DP does exactly that in dimensions. Each dimension has length 2, so "prefix sum along dimension " is a single addition: the cell with bit = 1 adds the cell with bit = 0.

flowchart LR
    subgraph p0["pass bit 0"]
        a0["000"] --> a1["001"]
        a2["010"] --> a3["011"]
        a4["100"] --> a5["101"]
        a6["110"] --> a7["111"]
    end
    subgraph p1["pass bit 1"]
        b0["000"] --> b2["010"]
        b1["001"] --> b3["011"]
        b4["100"] --> b6["110"]
        b5["101"] --> b7["111"]
    end
    subgraph p2["pass bit 2"]
        c0["000"] --> c4["100"]
        c1["001"] --> c5["101"]
        c2["010"] --> c6["110"]
        c3["011"] --> c7["111"]
    end

Each arrow means "the right cell adds the left cell's current value". Each pass pairs up masks that differ only in one bit.

The three-line algorithm

def sos(a, n):
    f = a[:]
    for i in range(n):                 # one dimension (bit) at a time
        for mask in range(1 << n):
            if mask >> i & 1:          # the "upper" cell in dimension i
                f[mask] += f[mask ^ (1 << i)]
    return f


assert sos([3, 1, 4, 1, 5, 9, 2, 6], 3) == [3, 4, 7, 9, 8, 18, 14, 31]

The outer loop must be over bits; the inner loop over masks. Swapping them is the most common SOS bug (see Pitfalls).

Mechanics

Trace: the three passes on the example

Columns are masks 000 … 111 (bit 2 on the left). Each row shows the array after one pass. Bold cells changed in that pass.

After000001010011100101110111
start (A)31415926
bit 0344551428
bit 13479514722
bit 234798181431

Follow mask 101:

  • Start: A[101] = 9.
  • Bit 0 pass: 101 has bit 0 set, so it adds the current value of 100 (= 5): 14. It now holds A[100] + A[101] — all submasks that may differ from 101 only in bit 0.
  • Bit 1 pass: 101 has bit 1 clear, so it does nothing. Still 14. (It holds submasks that may differ in bits 0 and 1 — but bit 1 is 0 in 101, so there is nothing new.)
  • Bit 2 pass: bit 2 set, add the current value of 001 (= 4, which is A[000] + A[001] after the bit 0 pass): 18 = 3 + 1 + 5 + 9. ✔

And 111 ends at 31, the sum of the whole array. Every final value matches the direct definition.

What each cell holds in the middle (the invariant)

After processing bits , the cell for mask holds

In words: the low bits are "free" (may drop from 1 to 0), the high bits are "frozen" (must equal mask's). Initially no bit is free: . At the end all bits are free: .

flowchart LR
    S0["S_0 = A : all bits frozen"] -->|"free bit 0"| S1["S_1"]
    S1 -->|"free bit 1"| S2["S_2"]
    S2 -->|"..."| Sn["S_n = F : all bits free"]

Superset sums

Flip the roles: for every mask, sum over all supersets (masks containing it).

Same loops; a cell with bit clear adds the cell with bit set:

def sos_superset(a, n):
    g = a[:]
    for i in range(n):
        for mask in range(1 << n):
            if not mask >> i & 1:
                g[mask] += g[mask | (1 << i)]
    return g


assert sos_superset([3, 1, 4, 1, 5, 9, 2, 6], 3) == [31, 17, 13, 7, 22, 15, 8, 6]

Check G[011] = A[011] + A[111] = 1 + 6 = 7 ✔ and G[000] = total = 31 ✔. (Superset sums are subset sums on complemented indices: G[m] = F'[~m] where F' is the subset sum of the array reversed. Either view works.)

The inverse: Möbius transform

Given F (sums over submasks), recover A. Undo each pass: subtract instead of add.

def mobius(f, n):
    a = f[:]
    for i in range(n):
        for mask in range(1 << n):
            if mask >> i & 1:
                a[mask] -= a[mask ^ (1 << i)]
    return a


assert mobius([3, 4, 7, 9, 8, 18, 14, 31], 3) == [3, 1, 4, 1, 5, 9, 2, 6]
After000001010011100101110111
start (F)34798181431
bit 031728101417
bit 1314181067
bit 231415926

Why does this work? Each forward pass is the linear map "upper cell += lower cell" applied to independent pairs. Its inverse is "upper cell −= lower cell" on the same pairs. The passes for different bits commute (each acts on a different coordinate, like row sums and column sums in 2-D), so undoing them in the same order (bit 0 first) is fine.

Written out, the Möbius transform is inclusion–exclusion:

For mask = 101: ✔. This is the main use of the inverse: when "at most" counts (sums over submasks) are easy and "exactly" counts are wanted, compute the easy ones and Möbius-transform.

Zeta and Möbius: the names

Name in combinatoricsFormulaSOS code
Subset zeta transform if bit set: f[m] += f[m ^ bit]
Subset Möbius transform if bit set: f[m] -= f[m ^ bit]
Superset zetaif bit clear: f[m] += f[m | bit]
Superset Möbiusif bit clear: f[m] -= f[m | bit]

Rota's theory defines and for any partially ordered set; the subset lattice is the special case where . You do not need the general theory, but the names appear in papers.

Convolutions: OR and AND

The OR convolution of two arrays is

If A and B are counts of values, C[x] counts pairs whose OR is exactly . Direct computation is . The zeta transform turns it into a pointwise product:

because exactly when and . So: zeta both, multiply pointwise, Möbius. in total. This is the bitwise analogue of "FFT, multiply, inverse FFT".

The AND convolution () works the same way with superset transforms, because exactly when and .

Worked example. Values [1, 2, 3, 4, 6], . Count ordered pairs (including ) by the exact value of a[i] | a[j].

000001010011100101110111
cnt01111010
cnt (values )01131235
squared (pairs with OR )011914925
Möbius (pairs with OR )01171276

Check OR = 3 directly: pairs from {1, 2, 3}: = 7 ✔. The row sums to 25 = , all ordered pairs ✔.

The ladder: brute force → better → optimal

Problem: compute F[mask] for all masks.

Rung 1: all pairs of masks,

def subset_sums_pairs(a, n):
    return [sum(a[s] for s in range(1 << n) if s & m == s) for m in range(1 << n)]

tests. : . Too slow beyond .

Rung 2: submask enumeration,

def subset_sums_submasks(a, n):
    f = [0] * (1 << n)
    for m in range(1 << n):
        s = m
        while True:
            f[m] += a[s]
            if s == 0:
                break
            s = (s - 1) & m
    return f


assert subset_sums_submasks([3, 1, 4, 1, 5, 9, 2, 6], 3) == [3, 4, 7, 9, 8, 18, 14, 31]

Visits only real (submask, mask) pairs: (why). : , fine. : , too slow.

Rung 3: SOS DP,

Dimension by dimension. : additions (half of the inner iterations actually add). Linear in the array size up to the factor .

Pairs Submasks SOS
101,048,57659,04910,240
164,294,967,29643,046,7211,048,576
203,486,784,40120,971,520
2231,381,059,60992,274,688
RungMethodTimeExtra spaceWhy it is better
1Test every pair of masksBaseline
2Enumerate submasksSkips pairs that are not submask relations
3SOS DP (in place)Shares partial sums across masks: each sum built from partial sums instead of terms

Is optimal? The output alone has numbers, so is a trivial lower bound; whether the extra factor is necessary for general algorithms is an open question (lower bounds of this kind are known only in restricted models such as bounded-coefficient linear circuits). In practice is the bound everyone uses, and nothing faster is known.

Correctness

Claim. After the pass for bit (0-indexed, passes run ), f[mask] , the sum over submasks of mask that agree with mask on bits .

Base. Before any pass, f = A = S_0 (no bit may differ, so the only "submask" counted is mask itself).

Step. Assume f = S_i before the pass for bit . Split the submasks counted by by their bit :

  • If bit of mask is 0, every submask has bit = 0, so freeing bit adds nothing: . The code leaves the cell alone ✔.
  • If bit of mask is 1, a submask either keeps bit = 1 (those are exactly the terms of ) or has bit = 0 (those are exactly the terms of : agree with mask ^ (1<<i) on bits , free below). The two groups are disjoint and cover everything, so . The code adds exactly that ✔.

In-place safety. During the pass for bit , the code reads f[mask ^ (1<<i)], which has bit = 0. Cells with bit = 0 are never written in this pass. So every read sees , not a half-updated value, regardless of the order of masks inside the pass. This is why one array suffices.

End. After all passes, f = sum over all submasks = F. ∎

Inverse. The pass for bit is the map : (lower, upper) ↦ (lower, upper + lower) on each pair. Its inverse is (lower, upper) ↦ (lower, upper − lower). The forward transform is ; the commute (they act on different coordinates), so its inverse can be applied in any order of bits. The closed form with follows by expanding the product: each pass contributes either "keep" (+1) or "drop bit " (−1).

Complexity

OperationTimeSpace
Subset or superset zeta (SOS) loop iterations, additions, in place
Möbius (inverse)samesame
OR / AND convolution
Subset convolution (ranked, see Variations)
Submask enumeration, for comparison extra

There is no best or worst case: the loops do the same work for every input. Memory is the binding constraint for large : 32-bit integers are 16 MiB, 64-bit integers 32 MiB, and 64-bit integers 256 MiB.

Cache behaviour. For small , mask and mask ^ (1<<i) are close in memory; for large they are elements apart, but the inner loop still walks memory sequentially in two streams, so hardware prefetching keeps it fast. A SOS pass in C++ runs in a few tens of milliseconds.

Implementation

Subset and superset zeta transforms, their Möbius inverses, and an application (count ordered pairs with a & b == 0), each checked against the naive submask sums on 300 random arrays.

import random
from typing import List


def zeta_subset(a: List[int], n: int) -> List[int]:
    """f[m] = sum of a[s] over all submasks s of m."""
    f = a[:]
    for i in range(n):
        bit = 1 << i
        for m in range(1 << n):
            if m & bit:
                f[m] += f[m ^ bit]
    return f


def mobius_subset(f: List[int], n: int) -> List[int]:
    """Inverse of zeta_subset."""
    a = f[:]
    for i in range(n):
        bit = 1 << i
        for m in range(1 << n):
            if m & bit:
                a[m] -= a[m ^ bit]
    return a


def zeta_superset(a: List[int], n: int) -> List[int]:
    """g[m] = sum of a[s] over all supersets s of m."""
    g = a[:]
    for i in range(n):
        bit = 1 << i
        for m in range(1 << n):
            if not m & bit:
                g[m] += g[m | bit]
    return g


def mobius_superset(g: List[int], n: int) -> List[int]:
    a = g[:]
    for i in range(n):
        bit = 1 << i
        for m in range(1 << n):
            if not m & bit:
                a[m] -= a[m | bit]
    return a


def naive_subset(a: List[int], n: int) -> List[int]:
    f = [0] * (1 << n)
    for m in range(1 << n):
        s = m
        while True:                      # every submask of m, including 0
            f[m] += a[s]
            if s == 0:
                break
            s = (s - 1) & m
    return f


def count_and_zero_pairs(values: List[int], n: int) -> int:
    """Ordered pairs (i, j), i == j allowed, with values[i] & values[j] == 0."""
    cnt = [0] * (1 << n)
    for v in values:
        cnt[v] += 1
    f = zeta_subset(cnt, n)              # f[m] = how many values are submasks of m
    full = (1 << n) - 1
    return sum(f[full ^ v] for v in values)


def main() -> None:
    a = [3, 1, 4, 1, 5, 9, 2, 6]
    assert zeta_subset(a, 3) == [3, 4, 7, 9, 8, 18, 14, 31]
    assert zeta_superset(a, 3) == [31, 17, 13, 7, 22, 15, 8, 6]
    assert mobius_subset(zeta_subset(a, 3), 3) == a
    assert count_and_zero_pairs([1, 2, 3, 4, 6], 3) == 10

    rng = random.Random(7)
    for _ in range(300):
        n = rng.randint(0, 9)
        arr = [rng.randint(-50, 50) for _ in range(1 << n)]
        f = zeta_subset(arr, n)
        assert f == naive_subset(arr, n)
        assert mobius_subset(f, n) == arr
        g = zeta_superset(arr, n)
        full = (1 << n) - 1
        rev = naive_subset(arr[::-1], n)               # supersets of m = submasks of ~m, reversed
        assert g == [rev[full ^ m] for m in range(1 << n)]
        assert mobius_superset(g, n) == arr
        vals = [rng.randrange(1 << n) for _ in range(rng.randint(0, 12))]
        assert count_and_zero_pairs(vals, n) == sum(1 for x in vals for y in vals if x & y == 0)
    print("zeta:", zeta_subset(a, 3), "pairs:", count_and_zero_pairs([1, 2, 3, 4, 6], 3))


if __name__ == "__main__":
    main()
import java.util.Arrays;
import java.util.Random;

public class SosDp {
    static long[] zetaSubset(long[] a, int n) {
        long[] f = a.clone();
        for (int i = 0; i < n; i++)
            for (int m = 0; m < (1 << n); m++)
                if ((m & (1 << i)) != 0) f[m] += f[m ^ (1 << i)];
        return f;
    }

    static long[] mobiusSubset(long[] f, int n) {
        long[] a = f.clone();
        for (int i = 0; i < n; i++)
            for (int m = 0; m < (1 << n); m++)
                if ((m & (1 << i)) != 0) a[m] -= a[m ^ (1 << i)];
        return a;
    }

    static long[] zetaSuperset(long[] a, int n) {
        long[] g = a.clone();
        for (int i = 0; i < n; i++)
            for (int m = 0; m < (1 << n); m++)
                if ((m & (1 << i)) == 0) g[m] += g[m | (1 << i)];
        return g;
    }

    static long[] mobiusSuperset(long[] g, int n) {
        long[] a = g.clone();
        for (int i = 0; i < n; i++)
            for (int m = 0; m < (1 << n); m++)
                if ((m & (1 << i)) == 0) a[m] -= a[m | (1 << i)];
        return a;
    }

    static long[] naiveSubset(long[] a, int n) {
        long[] f = new long[1 << n];
        for (int m = 0; m < (1 << n); m++) {
            for (int s = m; ; s = (s - 1) & m) {
                f[m] += a[s];
                if (s == 0) break;
            }
        }
        return f;
    }

    static long countAndZeroPairs(int[] values, int n) {
        long[] cnt = new long[1 << n];
        for (int v : values) cnt[v]++;
        long[] f = zetaSubset(cnt, n);
        int full = (1 << n) - 1;
        long total = 0;
        for (int v : values) total += f[full ^ v];
        return total;
    }

    static void check(boolean ok, String msg) { if (!ok) throw new AssertionError(msg); }

    public static void main(String[] args) {
        long[] a = {3, 1, 4, 1, 5, 9, 2, 6};
        check(Arrays.equals(zetaSubset(a, 3), new long[]{3, 4, 7, 9, 8, 18, 14, 31}), "zeta");
        check(Arrays.equals(zetaSuperset(a, 3), new long[]{31, 17, 13, 7, 22, 15, 8, 6}), "superset");
        check(Arrays.equals(mobiusSubset(zetaSubset(a, 3), 3), a), "mobius");
        check(countAndZeroPairs(new int[]{1, 2, 3, 4, 6}, 3) == 10, "pairs");

        Random rng = new Random(7);
        for (int iter = 0; iter < 300; iter++) {
            int n = rng.nextInt(10);
            long[] arr = new long[1 << n];
            for (int m = 0; m < (1 << n); m++) arr[m] = rng.nextInt(101) - 50;
            long[] f = zetaSubset(arr, n);
            check(Arrays.equals(f, naiveSubset(arr, n)), "zeta random");
            check(Arrays.equals(mobiusSubset(f, n), arr), "mobius random");
            long[] g = zetaSuperset(arr, n);
            int full = (1 << n) - 1;
            for (int m = 0; m < (1 << n); m++) {
                long direct = 0;
                for (int s = 0; s < (1 << n); s++) if ((s & m) == m) direct += arr[s];
                check(g[m] == direct, "superset random");
            }
            check(Arrays.equals(mobiusSuperset(g, n), arr), "superset mobius random");
            int k = rng.nextInt(13);
            int[] vals = new int[k];
            for (int i = 0; i < k; i++) vals[i] = rng.nextInt(1 << n);
            long brute = 0;
            for (int x : vals) for (int y : vals) if ((x & y) == 0) brute++;
            check(countAndZeroPairs(vals, n) == brute, "pairs random");
        }
        System.out.println("zeta: " + Arrays.toString(zetaSubset(a, 3)) + " pairs: " + countAndZeroPairs(new int[]{1, 2, 3, 4, 6}, 3));
    }
}
#include <cassert>
#include <cstdint>
#include <iostream>
#include <random>
#include <vector>
using namespace std;

using Vec = vector<int64_t>;

Vec zetaSubset(Vec f, int n) {
    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)];
    return f;
}

Vec mobiusSubset(Vec a, int n) {
    for (int i = 0; i < n; ++i)
        for (int m = 0; m < (1 << n); ++m)
            if (m >> i & 1) a[m] -= a[m ^ (1 << i)];
    return a;
}

Vec zetaSuperset(Vec g, int n) {
    for (int i = 0; i < n; ++i)
        for (int m = 0; m < (1 << n); ++m)
            if (!(m >> i & 1)) g[m] += g[m | (1 << i)];
    return g;
}

Vec mobiusSuperset(Vec a, int n) {
    for (int i = 0; i < n; ++i)
        for (int m = 0; m < (1 << n); ++m)
            if (!(m >> i & 1)) a[m] -= a[m | (1 << i)];
    return a;
}

Vec naiveSubset(const Vec& a, int n) {
    Vec f(1 << n, 0);
    for (int m = 0; m < (1 << n); ++m)
        for (int s = m;; s = (s - 1) & m) {
            f[m] += a[s];
            if (s == 0) break;
        }
    return f;
}

int64_t countAndZeroPairs(const vector<int>& values, int n) {
    Vec cnt(1 << n, 0);
    for (int v : values) cnt[v]++;
    Vec f = zetaSubset(cnt, n);
    int full = (1 << n) - 1;
    int64_t total = 0;
    for (int v : values) total += f[full ^ v];
    return total;
}

int main() {
    Vec a = {3, 1, 4, 1, 5, 9, 2, 6};
    assert((zetaSubset(a, 3) == Vec{3, 4, 7, 9, 8, 18, 14, 31}));
    assert((zetaSuperset(a, 3) == Vec{31, 17, 13, 7, 22, 15, 8, 6}));
    assert(mobiusSubset(zetaSubset(a, 3), 3) == a);
    assert(countAndZeroPairs({1, 2, 3, 4, 6}, 3) == 10);

    mt19937 rng(7);
    for (int iter = 0; iter < 300; ++iter) {
        int n = rng() % 10;
        Vec arr(1 << n);
        for (auto& x : arr) x = int64_t(rng() % 101) - 50;
        Vec f = zetaSubset(arr, n);
        assert(f == naiveSubset(arr, n));
        assert(mobiusSubset(f, n) == arr);
        Vec g = zetaSuperset(arr, n);
        for (int m = 0; m < (1 << n); ++m) {
            int64_t direct = 0;
            for (int s = 0; s < (1 << n); ++s)
                if ((s & m) == m) direct += arr[s];
            assert(g[m] == direct);
        }
        assert(mobiusSuperset(g, n) == arr);
        vector<int> vals(rng() % 13);
        for (auto& v : vals) v = rng() % (1 << n);
        int64_t brute = 0;
        for (int x : vals)
            for (int y : vals) brute += (x & y) == 0;
        assert(countAndZeroPairs(vals, n) == brute);
    }
    cout << "all SOS checks passed, pairs = " << countAndZeroPairs({1, 2, 3, 4, 6}, 3) << "\n";
}
function zetaSubset(a: number[], n: number): number[] {
  const f = a.slice();
  for (let i = 0; i < n; i++)
    for (let m = 0; m < (1 << n); m++)
      if (m & (1 << i)) f[m] += f[m ^ (1 << i)];
  return f;
}

function mobiusSubset(f: number[], n: number): number[] {
  const a = f.slice();
  for (let i = 0; i < n; i++)
    for (let m = 0; m < (1 << n); m++)
      if (m & (1 << i)) a[m] -= a[m ^ (1 << i)];
  return a;
}

function zetaSuperset(a: number[], n: number): number[] {
  const g = a.slice();
  for (let i = 0; i < n; i++)
    for (let m = 0; m < (1 << n); m++)
      if (!(m & (1 << i))) g[m] += g[m | (1 << i)];
  return g;
}

function mobiusSuperset(g: number[], n: number): number[] {
  const a = g.slice();
  for (let i = 0; i < n; i++)
    for (let m = 0; m < (1 << n); m++)
      if (!(m & (1 << i))) a[m] -= a[m | (1 << i)];
  return a;
}

function naiveSubset(a: number[], n: number): number[] {
  const f = new Array<number>(1 << n).fill(0);
  for (let m = 0; m < (1 << n); m++) {
    for (let s = m; ; s = (s - 1) & m) {
      f[m] += a[s];
      if (s === 0) break;
    }
  }
  return f;
}

function countAndZeroPairs(values: number[], n: number): number {
  const cnt = new Array<number>(1 << n).fill(0);
  for (const v of values) cnt[v]++;
  const f = zetaSubset(cnt, n);
  const full = (1 << n) - 1;
  return values.reduce((s, v) => s + f[full ^ v], 0);
}

function assert(ok: boolean, msg: string): void {
  if (!ok) throw new Error(msg);
}

const same = (x: number[], y: number[]) => x.length === y.length && x.every((v, i) => v === y[i]);

let seed = 7;
function rand(): number {                       // LCG, good enough for tests
  seed = (Math.imul(seed, 1103515245) + 12345) >>> 0;
  return seed / 4294967296;
}
const randInt = (lo: number, hi: number) => lo + Math.floor(rand() * (hi - lo + 1));

const a = [3, 1, 4, 1, 5, 9, 2, 6];
assert(same(zetaSubset(a, 3), [3, 4, 7, 9, 8, 18, 14, 31]), "zeta");
assert(same(zetaSuperset(a, 3), [31, 17, 13, 7, 22, 15, 8, 6]), "superset");
assert(same(mobiusSubset(zetaSubset(a, 3), 3), a), "mobius");
assert(countAndZeroPairs([1, 2, 3, 4, 6], 3) === 10, "pairs");

for (let iter = 0; iter < 300; iter++) {
  const n = randInt(0, 9);
  const arr = Array.from({ length: 1 << n }, () => randInt(-50, 50));
  const f = zetaSubset(arr, n);
  assert(same(f, naiveSubset(arr, n)), "zeta random");
  assert(same(mobiusSubset(f, n), arr), "mobius random");
  const g = zetaSuperset(arr, n);
  for (let m = 0; m < (1 << n); m++) {
    let direct = 0;
    for (let s = 0; s < (1 << n); s++) if ((s & m) === m) direct += arr[s];
    assert(g[m] === direct, "superset random");
  }
  assert(same(mobiusSuperset(g, n), arr), "superset mobius random");
  const vals = Array.from({ length: randInt(0, 12) }, () => randInt(0, (1 << n) - 1));
  let brute = 0;
  for (const x of vals) for (const y of vals) if ((x & y) === 0) brute++;
  assert(countAndZeroPairs(vals, n) === brute, "pairs random");
}
console.log("zeta:", zetaSubset(a, 3), "pairs:", countAndZeroPairs([1, 2, 3, 4, 6], 3));

All four keep the outer loop over bits and the inner loop over masks, transform in place on a copy, and use 64-bit (or double, exact below ) values because SOS sums of counts can reach . Under a modulus, reduce after each addition and add the modulus back after each subtraction in the Möbius pass.

Applications

Count pairs with a & b == 0

a & b == 0 means has no bit in common with , i.e. (the complement within bits). Let cnt[v] = how many times value occurs and F = ζ cnt. Then the number of compatible with is F[full ^ a[i]]. Sum over for ordered pairs. That is count_and_zero_pairs above.

For [1, 2, 3, 4, 6]: F = [0, 1, 1, 3, 1, 2, 3, 5]. Value 1 → complement 110 → 3 (namely 2, 4, 6). Value 2 → 101 → 2 (1, 4). Value 3 → 100 → 1 (4). Value 4 → 011 → 3 (1, 2, 3). Value 6 → 001 → 1 (1). Total ordered pairs, i.e. 5 unordered (no zeros, so no element pairs with itself).

If the problem wants unordered pairs with : subtract the self-pairs (only value 0 is compatible with itself, since ) and halve.

Count pairs with a | b == x, for every

The OR convolution of cnt with itself, from Convolutions: zeta, square, Möbius. The worked example above gives the full answer table.

For each element, find a partner with no common bit (Codeforces 165E "Compatible Numbers")

Up to numbers, each at most . For every , print any with , or . Counting is not enough; we need a witness. SOS works for any associative, commutative "sum" — here "sum" = "keep any non-empty value":

def compatible_numbers(values, n=22):
    witness = [-1] * (1 << n)
    for v in values:
        witness[v] = v
    for i in range(n):
        bit = 1 << i
        for m in range(1 << n):
            if m & bit and witness[m] == -1:
                witness[m] = witness[m ^ bit]       # any submask that is present
    full = (1 << n) - 1
    return [witness[full ^ v] for v in values]


res = compatible_numbers([10, 6, 9, 8, 2], n=4)
assert res[0] == -1                                  # 10 = 1010: nothing avoids both its bits
assert all(r == -1 or (r & v) == 0 for r, v in zip(res, [10, 6, 9, 8, 2]))
assert res[1:] != [-1] * 4

The same pattern with max instead of "any" gives "largest submask value", and with "top two" gives problems like AtCoder ARC 100 E (see the practice ladder). The requirement is that the combining operation is associative and commutative and that double counting is harmless or impossible. Each submask is reached along exactly one path through the passes, so sums are exact; for max/any, double counting would not matter anyway.

Groups whose AND is zero (Codeforces 449D "Jzzhu and Numbers")

Count non-empty subsets of the array whose AND is 0, modulo . Let = number of elements that are supersets of (superset zeta of counts). A group has AND iff every member is a superset of , so there are such non-empty groups. We want groups with AND exactly 0. Möbius over supersets, evaluated at 0:

def and_zero_groups(values, n, mod=10**9 + 7):
    g = [0] * (1 << n)
    for v in values:
        g[v] += 1
    for i in range(n):
        bit = 1 << i
        for m in range(1 << n):
            if not m & bit:
                g[m] += g[m | bit]
    total = 0
    for m in range(1 << n):
        term = pow(2, g[m], mod) - 1
        total += -term if bin(m).count("1") % 2 else term
    return total % mod


assert and_zero_groups([2, 3, 3], 2) == 0
assert and_zero_groups([0, 1, 2, 3], 2) == 10
assert and_zero_groups([5, 2, 0, 5, 2, 1], 3) == 53

Chromatic number in (Björklund–Husfeldt–Koivisto)

A graph is -colourable iff its vertex set can be covered by independent sets (a set of vertices with no edge inside). Let ind[S] = 1 if is independent, and = number of independent subsets of . By inclusion–exclusion, the number of ordered -tuples of independent sets whose union is all of is

and the graph is -colourable iff . One SOS pass plus work per : the whole chromatic number in , the best known bound ("Set partitioning via inclusion–exclusion", SIAM Journal on Computing 39(2), 2009).

def chromatic_number(n, edges):
    adj = [0] * n
    for a, b in edges:
        adj[a] |= 1 << b
        adj[b] |= 1 << a
    ind = [0] * (1 << n)
    ind[0] = 1
    for s in range(1, 1 << n):
        v = (s & -s).bit_length() - 1
        rest = s & (s - 1)
        ind[s] = 1 if ind[rest] and not (adj[v] & rest) else 0
    for i in range(n):                                  # i(S) = number of independent subsets of S
        for s in range(1 << n):
            if s >> i & 1:
                ind[s] += ind[s ^ (1 << i)]
    for k in range(1, n + 1):
        c = sum((-1) ** (n - bin(s).count("1")) * ind[s] ** k for s in range(1 << n))
        if c > 0:
            return k
    return 0


assert chromatic_number(5, [(i, (i + 1) % 5) for i in range(5)]) == 3        # odd cycle C5
assert chromatic_number(4, [(a, b) for a in range(4) for b in range(a + 1, 4)]) == 4   # K4
assert chromatic_number(4, [(0, 1), (1, 2), (2, 3), (3, 0)]) == 2            # even cycle C4

In production code use a modulus (or several) instead of Python big integers; can be huge.

Real-world uses

  • Frequent itemset mining. The support of an itemset in a transaction database is the number of transactions that contain — a superset sum over transaction masks. When the number of distinct items in a projected database is small, support counting for all itemsets at once is exactly superset SOS; Apriori and FP-growth avoid materialising arrays for large , but the underlying quantity is this transform (Agrawal and Srikant, "Fast Algorithms for Mining Association Rules", VLDB 1994).
  • Dempster–Shafer evidence theory. A mass function assigns weight to subsets of a frame of discernment; the belief of a set is the sum of masses of its subsets — the zeta transform — and the masses are recovered from beliefs by the Möbius transform. Kennes ("Computational aspects of the Möbius transformation of graphs", IEEE Trans. SMC 22(2), 1992) introduced the fast version used in evidence-fusion software.
  • Boolean functions in cryptography. The algebraic normal form (ANF) of a Boolean function — its representation as an XOR of AND-monomials — is obtained from the truth table by the Möbius transform over GF(2) (SOS with XOR instead of + and −). Tools such as SageMath's BooleanFunction.algebraic_normal_form() and S-box analysis scripts use this butterfly to compute the algebraic degree of cipher components.
  • Statistics: factorial designs. Yates' algorithm (1937) computes all main effects and interactions of a experiment with passes of pairwise sums and differences — the same dimension-by-dimension structure (with a Hadamard-style sign pattern).
  • Exact exponential algorithms. Chromatic number, counting perfect matchings, Steiner tree and set cover in all rest on zeta/Möbius transforms and their ranked versions (Björklund, Husfeldt, Kaski, Koivisto, "Fourier meets Möbius: fast subset convolution", STOC 2007).

Pitfalls and edge cases

  • Loops in the wrong order. for mask: for bit: is wrong: when you process mask 011 and add f[010], f[010] may not yet include its own submasks, or it may include them already and then a submask is counted twice. The outer loop must be over bits. Test with the example: the swapped order on [3,1,4,1,5,9,2,6] produces [3, 4, 7, 12, 8, 21, 17, 56] — F[111] comes out as 56 instead of 31 because small submasks are added several times.
  • Array too small. Values up to need (). full ^ v must stay inside the array: choose so that .
  • Overflow. Counts after SOS reach (number of elements); pair counts reach = for : use 64-bit. Squared zeta values in an OR convolution reach too.
  • Modular Möbius. After a[m] -= a[m ^ bit] under a modulus, add the modulus back if negative. In Python % handles it; in C++/Java it does not.
  • Self-pairs and order. "Pairs " vs "ordered pairs" vs " allowed": decide, then correct (subtract cnt[0] for the self-pairs of zeros in the a & b == 0 count, halve for unordered).
  • Using SOS when the operation is not a sum over containment. XOR conditions need the Walsh–Hadamard transform. "Max over submasks of dp[mask ^ s] + score[s]" (choosing a group) is not a sum-over-subsets; it needs submask enumeration.
  • Max/min SOS cannot be inverted. There is no Möbius transform for max. Only group operations (+, XOR) invert.
  • Python speed. means inner iterations: minutes in CPython. Use NumPy (f[mask_with_bit] += f[mask_without_bit] as array slices by reshaping to (2,)*n), PyPy, or C++.

Variations

  • Superset sums — shown above; flip the bit test.
  • Sum over submasks with bits removed / ranked transform. Keep a second index : f[k][m] = sum over submasks of size . This is the ranked zeta transform, the building block of the subset convolution.
  • Subset convolution. (disjoint unions only). Ranked zeta of both arrays, multiply as polynomials in the rank, ranked Möbius, keep the terms where . (Björklund–Husfeldt–Kaski–Koivisto 2007). It speeds up "partition into groups" DPs from to when the combination is a sum of products.
  • XOR convolution: the Walsh–Hadamard transform. . The same butterfly, but each pair (lower , upper ) becomes ; the inverse divides by . It is the Fourier transform on the group ; FFT & NTT covers the general Fourier version.
  • Generalised digits. The same dimension-by-dimension idea computes prefix sums over any product of small ranges, e.g. ternary masks (each digit 0/1/2): sum over "digit-wise ≤". That is just an -dimensional prefix sum.
  • SOS with other monoids. max, min, or, "top two", "any witness": all work forward; none has an inverse.

Practice ladder

Each problem is described in my own words; follow the link for the full statement.

1. Number of Valid Words for Each Puzzle (LeetCode 1178) — For each 7-letter puzzle, count words whose letters all appear in the puzzle and that contain the puzzle's first letter. Teaches the warm-up: when each query mask is tiny (7 bits → 128 submasks), plain submask enumeration over a hash map of word masks beats a SOS array.

Hint

Map every word to a 26-bit mask and count masks in a dictionary. For each puzzle, enumerate submasks of its 7-letter mask that contain the first letter, and sum the counts.

2. Triples with Bitwise AND Equal To Zero (LeetCode 982) — Count ordered triples of indices whose three values AND to zero (values below ). Teaches the AND convolution by superset zeta and the inclusion–exclusion at mask 0.

Solution

= number of values that are supersets of ; triples with AND : . Exactly 0: .

def count_triplets(nums, n=16):
    g = [0] * (1 << n)
    for v in nums:
        g[v] += 1
    for i in range(n):
        bit = 1 << i
        for m in range(1 << n):
            if not m & bit:
                g[m] += g[m | bit]
    return sum((-1) ** bin(m).count("1") * g[m] ** 3 for m in range(1 << n))


assert count_triplets([2, 1, 3], n=2) == 12
assert count_triplets([0, 0, 0], n=2) == 27

3. Bit Problem (CSES 1654) — For each of up to values (below ), count the elements with , with , and with . Teaches all three containment conditions in one problem.

Solution

⇔ : subset zeta. ⇔ : superset zeta. ⇔ not (): − subset zeta at the complement. bits.

def bit_problem(values, n=20):
    cnt = [0] * (1 << n)
    for v in values:
        cnt[v] += 1
    sub, sup = cnt[:], cnt[:]
    for i in range(n):
        bit = 1 << i
        for m in range(1 << n):
            if m & bit:
                sub[m] += sub[m ^ bit]
            else:
                sup[m] += sup[m | bit]
    full = (1 << n) - 1
    return [(sub[x], sup[x], len(values) - sub[full ^ x]) for x in values]


vals = [3, 7, 2, 9, 2]
assert bit_problem(vals, n=4) == [(3, 2, 5), (4, 1, 5), (2, 4, 4), (1, 1, 3), (2, 4, 4)]

(Python on takes a while; the official limits call for C++.)

4. Compatible Numbers (Codeforces 165E) — For each of up to numbers, output any other number with which it shares no set bit. Teaches SOS with a witness instead of a sum.

Hint

The compatible_numbers code above. 22 bits. Read input fast.

5. Or Plus Max (AtCoder ARC 100 E) — For every , the maximum of over with (indices are -bit masks). Teaches SOS over a "top two" monoid.

Solution

For each mask keep the two largest values among its submask indices (distinct indices). SOS merges top-two lists. The answer for is the running maximum of (top1 + top2) over masks , because "" is the union over masks of "".

def or_plus_max(a, n):
    top = [[(a[m], m)] for m in range(1 << n)]       # best (value, index) pairs, at most two
    for i in range(n):
        bit = 1 << i
        for m in range(1 << n):
            if m & bit:
                merged = {idx: val for val, idx in top[m] + top[m ^ bit]}
                top[m] = sorted(((v, k) for k, v in merged.items()), reverse=True)[:2]
    out, best = [], None
    for k in range(1, 1 << n):
        if len(top[k]) == 2:
            s = top[k][0][0] + top[k][1][0]
            best = s if best is None else max(best, s)
        out.append(best)
    return out


assert or_plus_max([1, 2, 3, 1], 2) == [3, 4, 5]
assert or_plus_max([10, 71, 84, 33, 6, 47, 23, 25], 3) == [81, 94, 155, 155, 155, 155, 155]

6. Yet Another Substring Reverse (Codeforces 1234F) — A string over the first 20 letters; you may reverse one substring; maximise the longest substring with all-distinct characters. Teaches "max over submasks" SOS combined with complements.

Hint

Reversal lets you join two disjoint distinct-character substrings. Mark every distinct-character substring's letter mask (at most of them), SOS-max the sizes over submasks, then for each marked mask combine with the best over submasks of .

7. Jzzhu and Numbers (Codeforces 449D) — Count non-empty groups with AND zero. Teaches superset zeta + inclusion–exclusion.

Hint

and_zero_groups above. 20 bits, , precompute powers of 2.

8. Vowels (Codeforces 383E) — Words of three letters from the first 24; for each of the vowel sets, count the words containing at least one vowel; output the XOR of the squares. Teaches "at least one" = total − "none", where "none" is a subset sum on the complement.

Hint

A word with letter set has no vowel from iff . SOS over (use 32-bit ints to fit in memory).

9. Bits And Pieces (Codeforces 1208F) — Maximise over . Teaches superset SOS keeping the two largest indices, plus a greedy over bits.

Hint

For each mask keep the two largest indices of elements that are supersets of it. For each from the left, greedily build the best (bits not in , high to low) such that two indices contain .

Common mistakes & interview follow-ups

"Why not just enumerate submasks?" That is ; SOS is . For : 3.5 billion vs 21 million. When the query masks are few or tiny (LeetCode 1178), enumeration wins; when you need every mask's answer, SOS wins.

"Prove the loop order matters." Give the invariant: after pass the low bits are free. With the loops swapped, mask 011 reads f[001] and f[010], both of which already include A[000], so A[000] is counted twice.

"How do you count pairs with a & b == x?" Superset zeta of counts, square pointwise, superset Möbius. Or, for a single , restrict to elements that are supersets of , strip 's bits, and count pairs with AND 0.

"What about XOR?" Walsh–Hadamard: same butterfly with .

"Can you do it with less memory?" The transform is in place: one array of . For counts that fit in 32 bits, use int arrays: ints = 64 MiB.

Mistakes interviewers watch for: swapped loops; an array of size instead of (so full ^ v is out of range); forgetting the self-pair or ordered/unordered correction; overflow in squared counts; trying to invert a max transform.

Quick quiz

1. After the bit 0 pass in the trace, cell 011 holds 5. Which original entries are in it?

Answer

A[010] + A[011] = 4 + 1 = 5: the submasks of 011 that may differ only in bit 0.

2. What is F[110] for the example, and which four entries make it up?

Answer

14 = A[000] + A[010] + A[100] + A[110] = 3 + 4 + 5 + 2.

3. Why is it safe to update f in place during a pass?

Answer

In the pass for bit only cells with bit set are written, and they read only cells with bit clear, which are not written in that pass.

4. You need, for each , the number of with x & y == x. Subset or superset SOS?

Answer

Superset: x & y == x means every bit of is in , i.e. .

5. Using the Möbius formula, recover A[110] from F = [3, 4, 7, 9, 8, 18, 14, 31].

Answer

✔.

6. Values go up to . How many bits, and how big is the SOS array?

Answer

, so 20 bits and an array of entries (4 MiB as 32-bit ints, 8 MiB as 64-bit).

Further reading / sources

  • usaxena95, "SOS Dynamic Programming [Tutorial]", Codeforces blog, 2016 — the tutorial that named the technique for competitive programmers.
  • Gian-Carlo Rota, "On the foundations of combinatorial theory I: Theory of Möbius functions", Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete 2, 1964.
  • Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto, "Fourier meets Möbius: fast subset convolution", STOC 2007.
  • Andreas Björklund, Thore Husfeldt, Mikko Koivisto, "Set partitioning via inclusion–exclusion", SIAM Journal on Computing 39(2), 2009.
  • Fedor V. Fomin and Dieter Kratsch, Exact Exponential Algorithms, Springer 2010 — Chapter 4 (inclusion–exclusion) and Chapter 7 (subset convolution, fast zeta and Möbius transforms).
  • Robert Kennes, "Computational aspects of the Möbius transformation of graphs", IEEE Transactions on Systems, Man, and Cybernetics 22(2), 1992.
  • Frank Yates, The Design and Analysis of Factorial Experiments, Imperial Bureau of Soil Science, 1937.
  • cp-algorithms, Enumerating submasks of a bitmask (the baseline).

Lessons: previous — Bitmask DP · next — Digit DP · module — Dynamic Programming · course — DSA: Zero to Mastery.

Related Archon pages: Prefix Sums · Bit Manipulation · Bitmask DP · Broken-Profile DP · FFT & NTT · Combinatorics.