DSA Tracker

Visualize

Partition Equal Subset Sum

time O(n * target)space O(target)

The key insight: 'split into two equal-sum subsets' reduces to a single reachability question — can some subset of the numbers add up to exactly half the total? dp[j] tracks whether sum j is reachable using the numbers processed so far; sweeping j from target down to num for every number (instead of up) ensures each number is only ever used once per subset, so it can't double-count the same item. If dp[target] ends up true, a valid equal split exists.

Details

Animated on: nums=[1,5,11,5], total sum=22, target=11, can array be partitioned?

Problem:Partition Equal Subset SumMedium

Dynamic Programming

step 1 / 8

1
[0]
0
[1]
0
[2]
0
[3]
0
[4]
0
[5]
0
[6]
0
[7]
0
[8]
0
[9]
0
[10]
0
[11]

Start: dp[0]=true, dp[1..11]=false, target=11 (half of total sum 22)

Pseudocode
1FUNCTION canPartition(nums):
2  total = the sum of all numbers in nums
3  IF total is odd: RETURN false
4  target = total / 2
5  dp = a list of target+1 falses (dp[j] = is sum j reachable)
6  dp[0] = true   (a sum of 0 is always reachable)
7  FOR each num in nums:
8    FOR j from target down to num:
9      dp[j] = dp[j] or dp[j-num]
10  RETURN dp[target]

← / → step · space play · Home restart

Every step in words

Show all 8 steps
  1. Start: dp[0]=true, dp[1..11]=false, target=11 (half of total sum 22)
  2. Process num=1, j=1 (right to left): dp[1] = dp[1] || dp[0] = false || true = true, first item makes sum 1 possible
  3. Process num=5, j=6: dp[6] = dp[6] || dp[1] = false || true = true (1+5=6); j=5: dp[5] = dp[5] || dp[0] = false || true = true (5=5)
  4. Process num=11, j=11: dp[11] = dp[11] || dp[0] = false || true = true, single element 11 reaches target sum
  5. Process second num=5, j=11: dp[11] = dp[11] || dp[6] = true || true = true (5+5+1=11, using both 5s and 1)
  6. Verify: subset {{11}} sums to 11, subset {{1,5,5}} also sums to 11, array can be partitioned into two equal-sum subsets
  7. Side effect: dp[10]=true (5+5=10) also achievable but target was dp[11]; partition still valid
  8. Answer: dp[11]=true, array CAN be partitioned into two equal-sum subsets: {{11}} and {{1,5,5}}

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Partition Equal Subset Sum in the editorAll Dynamic Programming problemsBack to roadmap