Decide whether an array can be split into two subsets with equal sums. Every number must go into exactly one of the two subsets.
DSA Animator › DSA Revision › Dynamic Programming › Partition Equal Subset Sum
Remember: equal partition means a subset with half the total. Loop sums downwards for 0 1 knapsack, so each item is used once. The video solves Partition Equal Subset Sum (LeetCode 416, Medium) with the 0/1 Knapsack pattern from the Dynamic Programming topic, and you can replay every step in the interactive Partition Equal Subset Sum animation.
Decide whether an array can be split into two subsets with equal sums. Every number must go into exactly one of the two subsets.
For 1, 5, 11, 5, the answer is true. The subsets 1, 5, 5 and 11 both add up to 11.
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.
The total is 22, so the target is 11, and only sum 0 is reachable at first. After the number 1, the reachable sums are 0 and 1. After 5, they are 0, 1, 5 and 6. After 11, sum 11 becomes reachable. The last 5 adds 10 as well, but 11 is already enough. So the answer is true.
In code, return false if the sum is odd, and set target to half of it. Create a boolean array of size target plus 1, with index 0 true. For each number, loop s from target down to the number, and set reachable of s to reachable of s or reachable of s minus the number. Return reachable of target, so it's O of n times target.
Remember: equal partition means a subset with half the total. Loop sums downwards for 0 1 knapsack, so each item is used once.