Why does the problem reduce to subset sum?

If the array splits into two parts with equal sums, each part adds up to total / 2. So the question becomes: does some subset add up to total / 2? The numbers left over automatically make the other half.

Why does the inner loop go from the target down?

Each number may be used once. Going down, dp[j − num] has not been updated for this number yet, so it still describes subsets without it. Going up would let the same number be added again and again, which is the unbounded knapsack.

What is the time complexity?

O(n · sum / 2): one pass over the dp row for each number. The row has total / 2 + 1 cells, so the space is O(sum).

Partition Equal Subset Sum

Decide whether an array splits into two halves with equal sums, using a 0/1 knapsack row of reachable sums filled right to left.

MediumSolve on LeetCode

Problem Understanding

Partition Equal Subset Sum: given an array of positive integers, return true if it can be split into two subsets whose sums are equal.

Examples: [1, 5, 11, 5] returns true ([1, 5, 5] and [11]). [1, 2, 3, 5] returns false: the total is 11, which is odd.

Attempt 1: Try Every Subset

Each number goes in the first half or the second, so there are 2^n ways to split. Checking them all works for tiny inputs, but n can be 200. Many of those subsets add up to the same sum, and only the sum matters: that is the overlap dynamic programming removes.

The Intuition: Which Sums Can We Make?

Both halves must add up to target = total / 2, so an odd total is an instant false. Otherwise, ask a smaller question: can some subset add up to target?

Keep a boolean row dp[0..target], where dp[j] means "some subset of the numbers seen so far adds up to j".

dp[0] = true: the empty subset.
For each num, any sum j that was reachable without it is still reachable, and j also becomes reachable if j − num was: dp[j] = dp[j] || dp[j − num].
Sweep j from target down to num. Then dp[j − num] still holds the old value, so num is counted at most once.

This is the 0/1 knapsack, with "can I make this weight" in place of "what is the best value".

Interactive Walkthrough

SUM 22, EACH HALF 11

BASE CASE

nums

num

—

Answer

—

The total is 22, so each half must add up to 11. dp[0] = true: the empty subset makes 0

Add 1. Sweep j from 11 down to 1, so 1 is used at most once

nums

The top row is the input, with the number being added marked. Below it, each cell of dp shows T when its sum is reachable. Watch the sweep run right to left: j reads dp[j − num], and a cell turns T the moment that one is.

Dry Run Table

Input: [1, 5, 11, 5], total 22, target 11

After adding	Reachable sums (dp[j] = T)
(start)	0
1	0, 1
5	0, 1, 5, 6
11	0, 1, 5, 6, 11
5	0, 1, 5, 6, 10, 11

dp[11] is true, so the answer is true: [11] on one side, [1, 5, 5] on the other.

The Solution Template

1D 0/1 knapsack over reachable sums, swept right to left.

Partition Equal Subset Sum Code

1var canPartition = function(nums) {
2    const total = nums.reduce((a, b) => a + b, 0);
3    if (total % 2) return false;
4    const target = total / 2;
5    const dp = new Array(target + 1).fill(false);
6    dp[0] = true;
7    for (const num of nums) {
8        for (let j = target; j >= num; j--) {
9            dp[j] = dp[j] || dp[j - num];
10        }
11    }
12    return dp[target];
13};

Edge Cases & Common Mistakes

Odd total: return false before building anything.
Sweeping left to right: dp[j − num] may already include this num, so one number gets counted twice. [1, 2, 5] would wrongly reach 4 as 2 + 2.
A number larger than the target: the inner loop simply does not run for it; no special case needed.
Forgetting dp[0] = true: without the empty subset nothing ever becomes reachable.

Summary

Equal halves means a subset adds up to total / 2. Track which sums are reachable in one boolean row, add each number with a right-to-left sweep so it is used once, and return dp[total / 2]. O(n · sum) time, O(sum) space.

More practice: DSA interview questions with answers · patterns cheat sheet

Combination Sum IV

Target Sum