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

• Which pattern gave this away within 90 seconds?
• What changed from the standard template?
• What would break the current solution?