Target Sum

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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.