Approach Summary
0/1 Knapsack variant. Target = totalSum/2. dp[j] = "can we form sum j?" using boolean DP on a 1D array.
How to Recognize This Pattern
- "Can array be split into two equal-sum subsets"
- 0/1 Knapsack: each item used at most once
Complexity Analysis
Time Complexity
O(n × sum/2)
Space Complexity
O(sum/2)
Tags
Array Dynamic Programming