Given an integer array nums, return true if you can split it into two subsets with equal sums, otherwise false. Every element goes into exactly one subset.
nums = [1,5,11,5]true ([1,5,5] and [11], both sum to 11)nums = [1,2,3,5]false (the total 11 is odd)target = total / 2; dp[0] = true (the empty subset)x, for s = target … x (right to left): dp[s] |= dp[s − x]dp[target] is true → return true 🎯With coin 2, going left-to-right would make 2 reachable, then use that same round's 2 to reach 4, then 6… that's using the coin again and again (the unbounded knapsack). Going right-to-left, every dp[s − x] you read is still from the previous coins, so each coin is used at most once: the 0/1 knapsack.
Odd total → impossible, no DP needed. Even total but no subset (e.g. [2,2,3,5], target 6) → the DP finishes without lighting 🎯. One element larger than target → false straight away. A single element can never be split.
Trying every subset is 2 to the power n. But only the sums matter, and they are bounded.
If the total is odd, it is impossible. Otherwise, the question becomes: is there a subset that adds up to half the total? Keep a boolean array where reachable of s is true when some subset sums to s. For each number, update the array from high sums down to low ones. Going downwards makes sure each number is used at most once.
Equal partition means a subset with half the total. Loop sums downwards for 0 1 knapsack, so each item is used once.
Run the animation above on your own input, or watch the 1:49 video explanation of Partition Equal Subset Sum with a dry run and Java code.