Advanced Conceptsbitmasksubsetcounting

Sum over Subsets

Given an array indexed by every bitmask from 0 to 2^n - 1, compute for each mask the sum of array values at all masks that are subsets of it, meaning a subset mask has a 1 bit only where the original mask also does.

Do this lesson first: coin change

Example input

n = 3, A = [2, -3, 5, 1, 4, -6, 3, -2] (A[000] = 2, A[001] = -3, and so on up to A[111] = -2)

Expected output

F = [2, -1, 7, 5, 6, -3, 14, 4]; the page highlights the largest, F[110] = 14

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[i][mask] is the sum of A[sub] over the subsets sub of mask that agree with mask on every bit from i upward. In other words only the lowest i bits are allowed to differ, and only by being switched off. Row 0 allows no bit to vary, so the only subset it counts for each mask is the mask itself, and the row is A. Row n allows every bit to vary, so it counts every subset and holds the answer F. The rows in between are the trick: instead of jumping from one subset to all of them, the table opens up one bit at a time.

dp[i][mask] = dp[i - 1][mask] + (bit i - 1 set in mask ? dp[i - 1][mask with bit i - 1 cleared] : 0)

Look at bit i - 1, the newest bit allowed to vary. Every subset counted at dp[i][mask] either matches mask on that bit or does not. Those that match differ from mask only in the lower i - 1 bits, and that is exactly dp[i - 1][mask]. Those that do not match must have the bit switched OFF, which is only possible if mask has it ON; they then agree with mask-without-that-bit on every higher bit and differ only below, which is dp[i - 1][mask ^ bit]. If mask has the bit clear, a subset cannot switch it on, so the second group is empty and contributes 0. No subset is in both groups and none is in neither, so the two sums add.

Row 0 is given: dp[0][mask] = A[mask]. Every later cell reads only the row above it, at its own mask and at most one smaller mask, so filling top to bottom is enough. Each subset is counted exactly once, and the reason is worth seeing: a subset of mask is reached by switching off some set of mask's bits, and the table switches off bit i - 1 only in row i, so there is exactly one path down the rows for each subset.

Tabulation with n + 1 rows of 2^n cells, one addition per cell. The obvious alternative is to walk the subsets of every mask directly, and that touches 2^(number of 1 bits) subsets per mask, 3^n in total: 3,486,784,401 at n = 20 against 20 × 2^20 = 20,971,520 additions here. The rows are also unnecessary in practice. Keep one array F, and for each bit in turn add F[mask ^ bit] into every mask that has the bit; that works in place, because the cells being read have the bit clear and are never the ones being written in that pass.

Time O(n × 2^n)Space O(n × 2^n), reducible to O(2^n) in place

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

Rows ↓
Cols →

000

001

010

011

100

101

110

111

-3

-6

-2

-1

-2

-1

-2

-1

-3

Rows ↓i: how many low bits are allowed to vary so far

Cols →mask, highest bit first

sum-over-subsets.ts

1function sumOverSubsets(A, n) {
2 const dp = [A.slice(0, 1 << n)]; // row 0: each mask counts only itself
3 for (let i = 1; i <= n; i++) {
4 const bit = 1 << (i - 1);
5 dp[i] = [];
6 for (let mask = 0; mask < 1 << n; mask++) {
7 const dropped = mask & bit ? dp[i - 1][mask ^ bit] : 0;
8 dp[i][mask] = dp[i - 1][mask] + dropped;
9 }
10 }
11 return dp[n]; // F[mask] for every mask
12}

Base caseComputedBeing readAnswer

The code, the trap, the variations

sum-over-subsets.ts

1function sumOverSubsets(A, n) {
2 const dp = [A.slice(0, 1 << n)]; // row 0: each mask counts only itself
3 for (let i = 1; i <= n; i++) {
4 const bit = 1 << (i - 1);
5 dp[i] = [];
6 for (let mask = 0; mask < 1 << n; mask++) {
7 const dropped = mask & bit ? dp[i - 1][mask ^ bit] : 0;
8 dp[i][mask] = dp[i - 1][mask] + dropped;
9 }
10 }
11 return dp[n]; // F[mask] for every mask
12}

Where people go wrong

Swapping the two loops in the one-array version described under execution, so masks are the outer loop and bits the inner one. In the layered table of the snippet the swap happens to be harmless, because each row keeps its own copy; it is the in-place form people actually write that breaks. There it overcounts: by the time a mask is reached, the smaller masks it borrows from already hold their full subset sums, so a subset arrives once for every order in which its missing bits could be switched off, twice for a subset missing two bits and six times for 000 under 111. On this array F[111] comes out 20 instead of 4, and with every entry of A set to 1, which should count the 8 subsets of 111, it reports 16. In place, the bit has to be the outer loop.

Sum over SUPERSETS instead: for each mask, add A at every mask that contains it.
Same rows, same one-bit-at-a-time idea, mirrored. A cell whose bit i - 1 is CLEAR adds the cell with that bit set, and a cell whose bit is set adds 0. The table then reads larger masks rather than smaller ones, and the in-place version still works for the mirrored reason: the cells read have the bit set and are never the ones written in that pass.
Count pairs of array elements x and y with x AND y equal to x.
Put each value's count into A, run this table, and F[y] is how many elements are subsets of y; summing F[y] over every element y gives the ordered pairs, an element paired with itself included. The table itself does not change at all, only what goes in and what is read out.
Use more bits.
Nothing changes in the method, but the columns double with every bit: 16 at four bits, past this page's 12-column budget, which is why it stops at three.

Digit DP