Problem Statement
Partition Equal Subset Sum
You get an array of whole numbers called nums. The question is simple to say: can you split the numbers into two groups so that each group adds up to the exact same total? For example, can one pile and another pile weigh the same? Here is the key trick. If both groups have the same total, then each group must add up to exactly half of everything. So the real question becomes: can I pick some of the numbers that add up to half the total? Two helpful facts fall out of this. First, if the total of all numbers is odd, you can never split it into two equal whole halves, so the answer is automatically false. Second, finding a group that hits "half the total" is a classic kind of puzzle called a 0/1 knapsack. "0/1" just means each number is either used (1) or not used (0), you cannot use a number twice and you cannot use half a number. We will solve it with dynamic programming, which means we build up answers to small versions of the problem and reuse them instead of redoing work.
Signals to notice
Brute force first
Try all 2^n subsets and check if any sums to total/2. That instinct is useful because it follows the prompt literally, but it usually keeps revisiting work the problem is begging you to organize.
The key insight
DP: dp[j] = true if a subset sums to j. For each number, update dp right-to-left: dp[j] = dp[j] || dp[j - num]. Target = totalSum / 2. Once you hold onto the right piece of information from moment to moment, the problem feels less like trial and error and more like following a shape that was there all along.
Trace it on nums=[1,5,11,5]
total=22 (even), target=22/2=11. dp=[T,F,F,F,F,F,F,F,F,F,F,F] (only dp[0]=T)
num=1: s=11..1, dp[1]|=dp[0] -> reachable sums {0,1}
num=5: s=11..5, dp[6]|=dp[1], dp[5]|=dp[0] -> {0,1,5,6}
num=11: s=11, dp[11]|=dp[0] -> {0,1,5,6,11}; dp[target] now T
num=5: s=11..5, dp[10]|=dp[5] -> {0,1,5,6,10,11}
return dp[11] = True (subset {1,5,5}=11)What must stay true
If any subset sums to totalSum/2, the remaining elements also sum to totalSum/2 — so we only need to find ONE subset with the target sum. This is exactly the 0/1 knapsack problem with the target as capacity. When you keep that truth intact, each local choice supports the larger solution instead of fighting it.
Shape of the loop
total = sum(nums); if total is odd: return false
target = total / 2; dp = boolean[target+1]; dp[0] = true
for num in nums:
for s from target down to num: # reverse keeps it 0/1
dp[s] = dp[s] or dp[s - num]
return dp[target]Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Not checking if totalSum is odd — if odd, equal partition is impossible (two integers can't sum to an odd number). Return false immediately. The fix is usually to return to the meaning of each move, not just the steps themselves.