Sum over Subsets DP

Sum Over Subsets (SOS) is technique used to efficiently calculate the sum of values for all subsets of a given set or bitmask. Instead of manually generating every subset, which can be slow, SOS uses bitwise operations to quickly go through only the necessary subsets.

The main trick is that for any bitmask $x$, we can directly loop through all its subsets $i$ using:

This ensures we efficiently handle only the subsets of $x$, skipping unnecessary combinations.

Implementation

Consider an array $A$ of $2^n$ elements. For a bitmask $x$, we define $F(x)$ as the sum of $A[i]$ over all subset mask $i \subseteq x$. That is:

The goal is to compute $F(x)$ for all $x = 0, 1, 2, ...., 2^n - 1$.

Solution

Brute Force

The naive solution is to iterate over all pair of masks, summing $A[i]$ only when one of them is a subset of the other (i.e.,$i \& x = i$).

Copy
vector<int> sos(1 << n);

for (int x = 0; x < (1 << n); x++) {
    // iterate over all other sets and checks whether they're a subset of x
    for (int i = 0; i < (1 << n); i++) {
        if ((i & x) == i) {
            sos[x] += a[i];
        }
    }
}

Copy
sos = [0] * (1 << n)
for x in range(1 << n):
	# iterate over all other sets and checks whether they're a subset of x
	for i in range(1 << n):
		if (x &i) == i:
			sos[x] += a[i]

This solution has a time complexity of $\mathcal{O}(2^n \cdot 2^n) = O(4^n)$, which is impractical for large $n$.

Optimized Solution

Instead of iterating over all $2^n$ bitmasks for $i$, we can optimize by iterating only over the subset mask of $x$.

Copy
vector<int> sos(1 << n);

for (int x = 0; x < (1 << n); x++) {
	sos[x] = a[0];
	// iterate over all subsets of x directly
	for (int i = x; i > 0; i = (i - 1) & x) {
		sos[x] += a[i];
	}
}

Copy
sos = [0] * (1 << n)
for x in range(1 << n):
	sos[x] = a[0]
	i = x
	# iterate over all subsets of x directly
	while i > 0:
		sos[x] += a[i]
		i = (i - 1) & x

Time Complexity: $\mathcal{O}(3^n)$

Faster Solution using Dynamic Programming

The above solution still has redundancy. For example, if a bitmask $i$ has $k$ unset bits, then $A[i]$ is summed $2^k$ times. If we precompute and reuse these sums, we can eliminate repeated additions.

Subset Mask Partitioning with $S(x, i)$

We define the subset $S(x, i)$ as follows:

In simpler terms, $S(x, i)$ contains all subset masks of $x$ whose bits to the left of the $i$-th bit match those of $x$.

For example:

The subsets $S(x, i)$ can be recursively partitioned as follows:

1. If the $i$-th bit of $x$ is $0$, then $S(x, i) = S(x, i - 1)$.
2. If the $i$-th bit of $x$ is $1$:

• Subsets with the $i$-th bit $1: S(x, i - 1)$.
• Subsets with the $i$-th bit $0 : S(x \oplus 2^i, i - 1)$.

Thus:

Using the above partitioning, we define a DP table $dp[x][i]$ where:

Time Complexity: $\mathcal{O}(N \cdot 2^N)$

Copy
vector<int> sos(1 << n);
vector<vector<int>> dp(1 << n, vector<int> (n));

for (int x = 0; x < (1 << n); x++) {
	dp[x][0] = a[x];
	if (x & 1) {
		dp[x][0] += a[x ^ 1];
	}
	for (int i = 1; i < n; i++) {
		dp[x][i] = dp[x][i - 1];

Copy
sos = [0] * (1 << n)
dp = [[0] * n for _ in range(1 << n)]

for x in range(1 << n):
	dp[x][0] = a[x]
	if x & 1:
		dp[x][0] += a[x ^ 1]

	for i in range(1, n):
		dp[x][i] = dp[x][i - 1]
		if x & (1 << i):
			dp[x][i] += dp[x ^ (1 << i)][i - 1]

	sos[x] = dp[x][n - 1]

Optimized Memory Usage

Since $dp[x][i]$ only depends on $dp[x][i - 1]$, we can reuse the DP array.

Copy
for (int i = 0; i < (1 << n); i++) {
	sos[i] = a[i];
}

for (int i = 0; i < n; i++) {
	for (int x = 0; x < (1 << n); x++) {
		if (x & (1 << i)) {
			sos[x] += sos[x ^ (1 << i)];
		}
	}
}

Copy
sos = [0] * (1 << n)
    for i in range(1 << n):
        sos[i] = a[i]

    for i in range(n):
        for x in range(1 << n):
            if x & (1 << i):
                sos[x] += sos[x ^ (1 << i)]

General Problems