Medium · Subset-Sum DP
Understand → Visualise → Practice.
Return whether positive integers can be split into two subsets with equal sums.
Splitting into equal halves is the same as finding a subset that sums to total / 2. Track every reachable subset sum as you consider each number once.
If the total is odd, equal halves are impossible.
Start with {0}. For each number, add it to every reachable sum that stays ≤ target (iterate sums downwards in an array version).
Return whether total / 2 became reachable.
O(n × target) time and O(target) space.
Updating the same DP states forward can reuse one number multiple times.
Read the full guide first: Dynamic Programming.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.