MediumNeetCode150ArrayDynamic Programming
Partition Equal Subset Sum
Check if array can be partitioned into two equal sum subsets.
Examples
Input
nums = [1,5,11,5]
Output
true
[1,5,5] and [11] both sum to 11.
Constraints
- •
1 <= nums.length <= 200 - •
1 <= nums[i] <= 100
Approaches
Include/exclude each element.
CodeT: O(2^n) | S: O(n) stack
dp[j] = can form sum j.
CodeT: O(n * target) | S: O(target)
1D boolean array.
CodeT: O(n * target) | S: O(target)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Recursion | O(2^n) | O(n) stack | Include/exclude each element. |
| DP Subset Sum | O(n * target) | O(target) | dp[j] = can form sum j. |
| DP Optimized | O(n * target) | O(target) | 1D boolean array. |
Recursion
T: O(2^n)S: O(n) stack
Include/exclude each element.
DP Subset Sum
T: O(n * target)S: O(target)
dp[j] = can form sum j.
DP Optimized
T: O(n * target)S: O(target)
1D boolean array.
Common Mistakes
Not checking odd sum
Wrong target calculation
Off-by-one in dp