Medium Problemssubsetpartition

Partition Problem

Given a set of positive integers, decide whether it can be split into two subsets whose sums are equal.

Example input

nums = [3, 1, 4]

Expected output

true (dp[3][4] = 1)

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] = dp[i - 1][s] or dp[i - 1][s - a_i], the second only when a_i <= s; target total / 2, and an odd total is no

The insight is the reduction. Splitting the numbers into two groups with equal totals is the same as choosing ONE group that adds to total / 2, because whatever is left over then adds to total / 2 as well. Once that is seen, the last decision is subset-sum's: the last number is either in the chosen group (read s - a_i in the row above) or not (read s in the row above), and either route reaching s is enough, which on 1s and 0s is a max. So the table never needs a column past total / 2.

Before any table: if the total is odd, the answer is no, because two equal whole-number totals add up to an even number. This page's numbers are chosen so every slider size has an even total, and its spec refuses an odd one rather than build a table for a question that is already answered. Row 0 is the only base row: dp[0][0] = 1 for the empty group, and every other row-0 cell is 0. Column 0 computes and is 1 all the way down. Fill row by row; both cells a cell reads are in the row above.

Tabulation over (n + 1) × (total / 2 + 1) cells, so the cost depends on how large the numbers are as well as how many there are. One row swept from high to low s is enough, exactly as in subset-sum. Once dp[i][total / 2] becomes 1 the answer is settled and the fill can stop early, because a later row's cell is at least the cell above it, so a 1 in that column is never cleared.

Time O(n × total)Space O(n × total), reducible to O(total) with one row swept from high to low

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.

Before any table: if the total is odd, the answer is no, because two equal whole-number totals add up to an even number. This page's numbers are chosen so every slider size has an even total, and its spec refuses an odd one rather than build a table for a question that is already answered. Row 0 is the only base row: dp[0][0] = 1 for the empty group, and every other row-0 cell is 0. Column 0 computes and is 1 all the way down. Fill row by row; both cells a cell reads are in the row above.

Rows ↓
Cols →

0

1

2

3

4

none

1

0

3

1

0

1

0

1

0

1

4

1

0

1

Rows ↓row i: may use the first i numbers

Cols →sum s: can one group make s?

partition-problem.ts

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

Base caseComputedBeing readAnswer

The code, the trap, the variations

partition-problem.ts

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

Where people go wrong

Dropping the odd-total check and letting integer division pick the target. Take [2, 3, 4]: the total is 9, Math.floor(9 / 2) is 4, the table finds {4}, and the program answers yes for numbers that cannot be split into equal halves at all, since 4 against 5 is not equal. The check costs one line and has to come before the table, because once the target is rounded the table is answering a different question correctly.

Minimize the difference between the two groups instead of requiring it to be zero.
The recurrence, the base row and the fill order are the same. The odd-total no goes, since every total now has an answer, and the columns run to floor(total / 2). Then find the largest s with dp[n][s] = 1; the smallest difference is total - 2s. That last step scans the final row, so the answer is no longer a single cell.
Count the ways to choose the first group.
Replace the or with a plus. The base row (dp[0][0] = 1, the empty group), the row-above reads and the fill order stay, and an odd total is now 0 ways. dp[n][total / 2] counts the subsets adding to half, and every split is counted twice, once from each side, so halve it.
Split into k groups with equal totals instead of two.
One subset-sum table no longer suffices, because the k groups must not share numbers and this table cannot see which numbers a 1 used. The usual approach makes the bitmask of numbers used so far the state; the current group's running total follows from it, as that mask's sum modulo total / k. That is 2^n states, a different state altogether, and the odd-total check becomes: if total is not divisible by k, the answer is no.

Box-Stacking Problem Longest Palindromic Subsequence