Partition Equal Subset Sum
Problem Description
Given a non-empty array nums of positive integers, determine if the array can be partitioned into two subsets with equal sum.
Example 1:
Input: nums = [1,5,11,5]
Output: true (subsets [1,5,5] and [11])
Example 2:
Input: nums = [1,2,3,5]
Output: false
DE Shaw Tier 1 — LC 416 (Subset Sum Partition, minimize abs diff of two subsets).
Optimal: 0/1 Knapsack DP O(n * sum/2) time and space.
If total sum is odd, immediately false.
Let target = sum/2. dp[j] = can we reach sum j using some subset.
Talk-track: 'This reduces to: can we find a subset summing to total/2? Classic 0/1 knapsack — iterate items outer, sums inner (right to left to avoid reuse).'
Example Test Cases
Example 1
Input: [[1,5,11,5]]
Expected: true
Example 2
Input: [[1,2,3,5]]
Expected: false
Example 3
Input: [[2,2,1,1]]
Expected: true
Example 4
Input: [[100]]
Expected: false
Run your code to see the results