Approach Summary
Count subsets with sum = (target + totalSum) / 2. DP over each number, updating counts of reachable sums.
How to Recognize This Pattern
- Assign + or − to each number, count ways to reach target
- Reduces to "count subsets with given sum"
Complexity Analysis
Time Complexity
O(n × sum)
Space Complexity
O(sum)
Tags
Array Dynamic Programming Backtracking