Target Sum
Problem
Put either + or − in front of every number, then add them all up. Return how many sign assignments give exactly target.
Example 1
Input: nums = [1, 1, 1, 1, 1], target = 3 Output: 5
Exactly one of the five numbers is negative.
Test cases
Case 1
Input: [1,1,1,1,1], 3 Expected: 5
Case 2
Input: [1], 1 Expected: 1
Case 3
Input: [1], 2 Expected: 0
View solutionHide solution1 approach
1. Reduce to subset-sum counting
Time O(n × sum)Space O(sum)
Let P be the "+" set: P − (total − P) = target, so P = (total + target) / 2. Count subsets with that sum (0/1 knapsack, iterate sums downward).
function findTargetSumWays(nums, target) { const total = nums.reduce((a, b) => a + b, 0); if (Math.abs(target) > total || (total + target) % 2) return 0; const P = (total + target) / 2; const dp = new Array(P + 1).fill(0); dp[0] = 1; for (const x of nums) for (let s = P; s >= x; s--) dp[s] += dp[s - x]; return dp[P];}Start with memoised recursion on (index, running sum) if the algebra does not come to you.