Easy Problemssubsetpartition

Subset Sum Problem

Given a set of n non-negative integers and a target value, decide whether some subset of the set adds up to exactly that target.

Do this lesson first: coin change

Example input

set = [3, 5, 7, 8], target = 6

Expected output

false (dp[4][6] = 0)

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. Two numbers name the state, how many of the numbers you may use and which total you are asking about, so the table is a grid: row 0 for no numbers, then one row per number, and one column per total from 0 up to the target. A cell is a yes or a no. It is not a count, and it does not record which numbers made the total.

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

Ask about the last number allowed, a_i. Every subset of the first i numbers either leaves it out or puts it in, and there is no third case. Leave it out, and the rest is a subset of the first i - 1 numbers adding to s: that is the cell straight above. Put it in, and the rest is a subset of the first i - 1 numbers adding to s - a_i: that is the cell a_i columns to the left in the row above. If either one says yes, s is reachable. On a table of 1s and 0s, either one being 1 is the same thing as the larger of the two being 1, so the animation writes the or as a max. When a_i is bigger than s, putting it in is impossible and the cell copies the one above. The flagship coin-change lesson teaches the same habit of asking what the last decision had to be; there the decision was which coin came last, here it is whether the last number is in.

Row 0 is the only base row. With no numbers allowed, the empty subset is the only subset, so dp[0][0] = 1 and the rest of row 0 is 0. Column 0 is not a base: it computes, and comes out 1 all the way down, because leaving every number out still makes 0. Fill row by row from the top. Both cells a cell reads sit in the row above, so they are final before anything reads them. It has to be the row ABOVE for the put-it-in case, not the current row: the current row's cell at s - a_i may already have used a_i, and reading it would let one number appear twice.

Tabulation over (n + 1) × (target + 1) cells. Every cell reads only the row above, so the grid collapses to a single row of target + 1 flags, as long as each pass sweeps s from the RIGHT, high totals first, so the cell at s - a_i still holds the previous row's value when s reads it. Sweeping left to right in that single row is the same use-a-number-twice bug as reading the current row in the grid. A memoized recursion over (i, s) gets the same answers and can visit far fewer cells, since it only asks about totals some chain of decisions actually reaches from the target; it pays for that with call overhead and recursion depth n, and it gives up the one-row space trick.

Time O(n × target)Space O(n × target), reducible to O(target) 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.

Row 0 is the only base row. With no numbers allowed, the empty subset is the only subset, so dp[0][0] = 1 and the rest of row 0 is 0. Column 0 is not a base: it computes, and comes out 1 all the way down, because leaving every number out still makes 0. Fill row by row from the top. Both cells a cell reads sit in the row above, so they are final before anything reads them. It has to be the row ABOVE for the put-it-in case, not the current row: the current row's cell at s - a_i may already have used a_i, and reading it would let one number appear twice.

Rows ↓
Cols →

0

1

2

3

4

5

6

none

1

0

3

1

0

1

0

5

1

0

1

0

1

0

7

1

0

1

0

1

0

8

1

0

1

0

1

0

Rows ↓row i: may use the first i numbers

Cols →target s: can some subset make s?

subset-sum.ts

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

Base caseComputedBeing readAnswer

The code, the trap, the variations

subset-sum.ts

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

Where people go wrong

Letting a number be used twice. The put-it-in case must read dp[i - 1][s - a_i], from the row above. Read dp[i][s - a_i] from the current row instead and the 3 can join a subset that already holds the 3: on this set that answers yes at target 6, from 3 + 3, and yes at target 9, from 3 + 3 + 3, where the true answer at both is no. That one changed row index is the entire difference between this problem and its use-any-number-again version, the shape coin-change-count-ways uses, so the bug produces a correct program for the wrong problem and nothing crashes. In the single-row version the same bug is sweeping s from left to right.

Count the subsets that add to the target instead of deciding whether one exists.
Replace the or with a plus and keep everything else: the same two cells, the same row-above rule, the same fill order. dp[0][0] = 1 now means one subset, the empty one, and the answer is a count rather than a flag.
Allow each number to be used any number of times.
The put-it-in case reads the current row, dp[i][s - a_i], because a_i is still available after it has been used once. That is the shape of coin-change-count-ways and unbounded-knapsack. The table's shape and the fill order do not change, only which row the second cell sits in.
Ask whether the numbers split into two groups with equal totals.
That is partition-problem. If the total is odd the answer is no without a table; otherwise it is this exact table with the target set to half the total, because one group adding to half leaves the rest adding to the other half.

Decode Ways Coin change problem – Count Ways