Target Sum

Problem (restated)

Assign + or - to each nums[i]. Count ways the signed sum equals target.

Intuition

Partition into positive set P and negative set N: P-N=target, P+N=sum ⇒ P=(sum+target)/2. Count subsets summing to P.

Approaches

export function findTargetSumWays(nums: number[], target: number): number {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total < Math.abs(target) || (total + target) % 2 !== 0) return 0;
  const need = (total + target) / 2;
  const dp = Array(need + 1).fill(0);
  dp[0] = 1;
  for (const x of nums) {
    for (let c = need; c >= x; c--) dp[c] += dp[c - x]!;
  }
  return dp[need]!;
}

export function findTargetSumWays(nums: number[], target: number): number {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total < Math.abs(target) || (total + target) % 2 !== 0) return 0;
  const need = (total + target) / 2;
  const dp = Array(need + 1).fill(0);
  dp[0] = 1;
  for (const x of nums) {
    for (let c = need; c >= x; c--) dp[c] += dp[c - x]!;
  }
  return dp[need]!;
}

Template connection

Subset-sum / 0/1 knapsack counting.

Reflection

• sum(P) - sum(N) = target and the total is fixed, so 2 * sum(P) = total + target. Count the subsets that make that sum(P).
• If total + target is odd, or the target lies outside the reachable range, the answer is 0. dp[0] = 1.
• A zero accepts either sign and produces the same sum twice. The question is the assignment of signs, not the order of numbers.