Medium Problemssubsetcounting

All distinct subset (or subsequence) sums

Given a set of n non-negative integers, find every distinct total that can be formed by adding up some subset of its elements, including the empty subset's total of zero.

Do this lesson first: coin change

Example input

nums = [2, 3, 5]

Expected output

0, 2, 3, 5, 7, 8, 10

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][s] is 1 if some subset of the first i numbers adds up to exactly s, and 0 if none does. That is subset-sum's state, with one change of reach: there the columns stopped at a target, and here they run all the way to the total of every number, because the question is about every total at once and no subset can make more than that. What is different is the answer. subset-sum reads one cell. This problem reads the WHOLE bottom row: every column whose last-row cell is 1 is a total some subset makes, and the list of those columns is the output. A cell is a yes or a no, so a total made two different ways is still a single 1, and that is where the word distinct is taken care of.

dp[i][s] = dp[i - 1][s] or dp[i - 1][s - a_i], the second only when a_i <= s

subset-sum's decision, unchanged: every subset of the first i numbers either leaves the last one, a_i, out, and then the rest makes s from the first i - 1 numbers (the cell above), or puts it in, and then the rest makes s - a_i from the first i - 1 numbers (a_i columns to the left in the row above). Either route reaching s is enough, and on 1s and 0s that is the larger of the two, which is why the animation writes it as a max. Nothing about the recurrence knows that the whole row will be read at the end; it fills every column the same way subset-sum fills the ones left of its target.

Row 0 is the only base row: with no numbers allowed the only subset is the empty one, so dp[0][0] = 1 and every other cell of row 0 is 0. Column 0 computes, and is 1 all the way down, since leaving everything out always makes 0; that is the empty subset's total the statement asks you to include. Fill row by row. Both cells a cell reads are in the row above, and the put-it-in read has to come from the row above rather than the current one, or a number can be used twice.

Tabulation over (n + 1) × (total + 1) cells, so the cost grows with how large the numbers are as well as how many there are. The alternative is to enumerate the 2^n subsets and collect their totals in a set. The table wins whenever the total is small next to 2^n, and it can never have more distinct answers to report than total + 1, since that is how many columns there are. Every cell reads only the row above, so one row of total + 1 flags is enough, swept from the right so that the cell at s - a_i still holds the previous row's value when s reads it. As on nth-row-of-pascals-triangle, and unlike pascals-triangle, where the earlier rows are the output, the reduction keeps everything the answer needs: the answer is the last row, and the last row is what the rolling row holds at the end. One step further, the row of flags can be packed into the bits of one integer, and then a whole row is reach | (reach << a_i), one shift and one or per number. That is the same table, a word at a time.

Time O(n × total)Space O(n × total), reducible to O(total) with one row swept right to left

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 →

none

Rows ↓row i: may use the first i numbers

Cols →total s: can some subset make s?

all-distinct-subset-sums.ts

1function allSubsetSums(nums) {
2 const n = nums.length;
3 const total = nums.reduce((a, b) => a + b, 0);
4 const dp = Array.from({ length: n + 1 }, () => new Array(total + 1).fill(0));
5 dp[0][0] = 1;
6 for (let i = 1; i <= n; i++) {
7 const a = nums[i - 1];
8 for (let s = 0; s <= total; s++) {
9 dp[i][s] = dp[i - 1][s];
10 if (a <= s) dp[i][s] = Math.max(dp[i][s], dp[i - 1][s - a]);
11 }
12 }
13 const sums = [];
14 for (let s = 0; s <= total; s++) if (dp[n][s] === 1) sums.push(s);
15 return sums;
16}

Base caseComputedBeing readAnswer

The code, the trap, the variations

all-distinct-subset-sums.ts

1function allSubsetSums(nums) {
2 const n = nums.length;
3 const total = nums.reduce((a, b) => a + b, 0);
4 const dp = Array.from({ length: n + 1 }, () => new Array(total + 1).fill(0));
5 dp[0][0] = 1;
6 for (let i = 1; i <= n; i++) {
7 const a = nums[i - 1];
8 for (let s = 0; s <= total; s++) {
9 dp[i][s] = dp[i - 1][s];
10 if (a <= s) dp[i][s] = Math.max(dp[i][s], dp[i - 1][s - a]);
11 }
12 }
13 const sums = [];
14 for (let s = 0; s <= total; s++) if (dp[n][s] === 1) sums.push(s);
15 return sums;
16}

Where people go wrong

Letting a number be used twice. Read the put-it-in cell from the current row, dp[i][s - a_i], instead of the row above, and a number can join a subset that already holds it. On [2, 3, 5] the bottom row then claims 4 (2 + 2), 6 (3 + 3) and 9 (2 + 2 + 5) as well, ten totals where the answer has seven: every total from 0 to 10 except 1. The output is still a sorted list of plausible-looking totals, so nothing looks broken; it is the right answer to a different problem, the one where each number may be reused. In the single-row version the same bug is sweeping s upwards.

Count how many subsets make each total instead of whether any does.
Replace the or with a plus and keep the table, the base row and the order. dp[0][0] = 1 now counts the empty subset, and on [2, 3, 5] the bottom row reads 1, 0, 1, 1, 0, 2, 0, 1, 1, 0, 1: the 2 in column 5 is the duplicate this page's yes or no quietly merges. The row adds up to 2^n, here 8, one for every subset.
Allow zeros among the numbers, as the statement's non-negative integers do.
A 0 changes nothing. Its put-it-in cell is the cell straight above, the same one its leave-it-out cell reads, so its row is a copy of the row above, and the distinct totals are exactly those of the other numbers. The usual code handles that without a special case; it is only worth dropping zeros first to save the copied rows.
Allow negative numbers.
The totals now run from the sum of the negatives up to the sum of the positives, so shift every column by the size of the negative sum and the table is the same skip-or-take table over a wider range. The put-it-in cell for a negative a_i sits to the RIGHT of the cell rather than the left, which does not matter while it is read from the row above, and matters a great deal in the one-row version, where the sweep must then run left to right for that number.

Longest Common Increasing Subsequence Count Derangements