Partition Equal Subset Sum — Step-by-Step Visualization

Algorithm Pattern

Dynamic Programming (Subset Sum with Set)

Key Idea

Track all reachable subset sums in a set. For each number, expand the set by adding that number to every existing sum. If the target (total/2) ever enters the set, return True.

Step-by-Step Approach

1. If total is odd, partition is impossible — return False.
2. target = total // 2.
3. dp = {0} (empty subset sum = 0).
4. For each n: dp = dp ∪ {s + n for s in dp}.
5. If target in dp, return True.
6. If target never reached, return False.

Common Gotchas

• Odd total is an immediate impossibility check.
• Early return when target is found avoids unnecessary work.