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.