PrevNext
Rare
 0/7

Sum over Subsets DP

Authors: Siyong Huang, Aakash Gokhale

Taking bitmask DP to the next level.

Edit This Page

Prerequisites


Resources
CF

Good explanation + problem list

GFG

Goes over brute force solutions

CF

Characterizing SOS DP as multidimensional prefix sums

Sum over subsets (SOS) DP is a trick that allows you to efficiently compute the sum of all the subsets of an array.

The naive solution would be to iterate through every pair of masks and check if one of them is a subset of the other.

C++

// # of elements in the list for which you want to find the sum over all subsets
int n = 20;
// the list for which you want to find the sum over all subsets
vector<int> a(1 << n);
// answer for sum over subsets of each subset
vector<int> sos(1 << n);
for (int i = 0; i < (1 << n); i++) {
// iterate over all other sets and checks whether they're a subset of i
for (int j = 0; j < (1 << n); j++) {
if ((i & j) == j) { sos[i] += a[j]; }
}
}

We can speed this up if we iterate over only subsets of the current mask and add up all of the those values to get the sum over subsets for a particular mask.

The difference comes from the fact that in the first example we iterate over every pair of subsets which takes (2n)2(2^n)^2 time and the second we iterate directly over the subsets for each mask. This means each mask is only visited by 2nk2^{n - k} other masks where k is the number of elements of the mask. This means that the total time complexity is O0n(nk)2nk=3n\sum_0^n {n \choose k} \cdot 2^{n - k} = 3^n).

C++

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

Notice how in both of these examples we don't seem to be saving much information between different subsets which is the essence of DP. Define SOS(mask,x)\texttt{SOS}(\texttt{mask}, x) to be the sum of subsets of mask such that the first xx bits of the subset are identical to the first xx bits of mask. For example, SOS(1001001,3)\texttt{SOS}(1001001, 3) includes the subsets 10010011001001, 10000011000001, 10010001001000, 10000001000000 which all have the same common prefix of 100100.

Let's try to figure out the transitions between different states.

If the xxth bit of mask is a 00 then we can only transition to this state if the xxth bit of the subset is also 00. If the xxth bit of the subset mask was a 11 then it would no longer be a subset.

If the xxth bit of mask is a 11 then we can transition to this state from both subsets where the xxth bit is turned off and turned on because both of these cases would be subsets.

More formally,

SOS(mask,x)={SOS(mask,x1)+SOS(mask2i,x1)if 2imask>0SOS(mask,x1)otherwise\texttt{SOS}(mask, x) = \left\{ \begin{array}{ c l } \texttt{SOS}(\texttt{mask}, x - 1) + \texttt{SOS}(\texttt{mask} - 2^i, x - 1) & \quad \textrm{if } |2^i \wedge \texttt{mask}| > 0 \\ \texttt{SOS}(\texttt{mask}, x - 1) & \quad \textrm{otherwise} \end{array} \right.

C++

int n = 20;
vector<int> a(1 << n);
// keeps track of the sum over subsets
// with a certain amount of matching bits in the prefix
vector<vector<int>> dp(1 << n, vector<int>(n));
vector<int> sos(1 << n);
for (int mask = 0; mask < (1 << n); mask++) {
dp[mask][-1] = a[mask];

Additional Problems

StatusSourceProblem NameDifficultyTags
CSESEasy
PlatEasy
Show TagsCombo, DP
CFNormal
Show TagsBitmasks, DP
PlatNormal
Show TagsNT, Prefix Sums
InfoArenaHard
Show TagsBitmasks, DP, NT
JOIHard
Show TagsSOS DP
CFInsane
Show TagsBitmasks, DP, SOS DP

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

PrevNext