Dynamic Programming • 0/1 Knapsack

Partition Equal Subset Sum

Determine if a given array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Overview

This is a classic variation of the Subset Sum / 0-1 Knapsack problem. If the total sum is odd, it's impossible. If it's even, we just need to find ANY subset that sums to exactly `Total / 2`.

The DP State

We use a 1D boolean array where `dp[j]` is `true` if a subset with sum `j` exists. The base case is `dp[0] = true`.

Reverse Traversal

When optimizing to 1D, we MUST iterate the target sum `j` backwards (from `target` down to `num`). This ensures we don't use the same element multiple times.

The Check

For a given `num`, we can reach sum `j` if we could already reach sum `j - num`. So `dp[j] = dp[j] || dp[j - num]`.

1

5

11

5

DP Array (Can Reach Sum j?)

0

T

1

F

2

F

3

F

4

F

5

F

6

F

7

F

8

F

9

F

10

F

11

F

Code Tracker

:::

1let sum = nums.reduce((a, b) => a + b, 0);

2if (sum % 2 !== 0) return false;

3let target = sum / 2;

4let dp = new Array(target + 1).fill(false);

5dp[0] = true;

6for (let num of nums) {

7 for (let j = target; j >= num; j--) {

8 dp[j] = dp[j] || dp[j - num];

9 }

10}

11return dp[target];