Pattern visualizer
Partition Equal Subset Sum
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. Animated on: nums=[1,5,11,5], total sum=22, target=11, can array be partitioned?.
Dynamic Programming
time O(n * target)space O(target)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]line 6
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 nums3 IF total is odd: RETURN false4 target = total / 25 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