Partition Equal Subset Sum

Partition Equal Subset Sum

What is this problem about?

The Partition Equal Subset Sum problem asks whether an array can be split into two subsets with equal sum. This is equivalent to asking: does any subset sum to total/2? This Partition Equal Subset Sum coding problem is the canonical 0/1 knapsack / subset sum problem. The array and dynamic programming interview pattern is the foundational skill tested.

Why is this asked in interviews?

Goldman Sachs, Microsoft, Meta, Amazon, Google, Bloomberg, and Adobe ask this because it's the classic subset sum problem that validates DP fundamentals. Every candidate should know both the 2D DP and the space-optimized 1D boolean DP approaches.

Algorithmic pattern used

0/1 Knapsack boolean DP. If total is odd, return false. Target = total/2. dp[j] = whether any subset sums to j. For each element num: update dp in reverse: dp[j] |= dp[j-num] for j from target down to num. Initialize dp[0]=true. Return dp[target].

Example explanation

arr=[1,5,11,5]. Total=22. Target=11. After processing 1: dp[1]=true. After 5: dp[6]=true,dp[5]=true. After 11: dp[11]=true (directly). Return true.

arr=[1,2,3,5]. Total=11. Target=5.5 (not integer). Return false.

Common mistakes candidates make

• Not checking total parity first.
• Forward DP update (allows same element used multiple times — must be reverse).
• Initializing dp[0]=false (must be true — empty subset has sum 0).
• Off-by-one in target computation.

Interview preparation tip

Partition Equal Subset Sum is the must-know DP problem for subset sum. Memorize the boolean DP with reverse iteration: it's the same as 0/1 knapsack. The space optimization reduces O(n * target) space to O(target). After mastering this, practice: "subset sum count," "minimum subset sum difference," "partition k equal subsets." They all extend this same boolean DP framework.