Target Sum

Assign sign to each number + or - to form target sum

Target Sum

Problem Statement

You are given an integer array, nums, and an integer, target.

Your goal is to build a mathematical expression using all the numbers in the array. For every number, you must place either a + (plus) or a - (minus) sign right before it.

After assigning the signs and evaluating the expression, the final sum must equal the target.

Return the total number of different expressions you can build that evaluate to the target.

Examples

Example 1

• Input: nums = [1, 1, 1, 1, 1], target = 3
• Output: 5
• Explanation: There are 5 ways to assign symbols to make the sum equal to 3:
  • -1 + 1 + 1 + 1 + 1 = 3
  • +1 - 1 + 1 + 1 + 1 = 3
  • +1 + 1 - 1 + 1 + 1 = 3
  • +1 + 1 + 1 - 1 + 1 = 3
  • +1 + 1 + 1 + 1 - 1 = 3

Example 2

• Input: nums = [1], target = 1
• Output: 1

The Core Idea: Reducing to Subset Sum

At first glance, this looks like a new problem. However, it is mathematically identical to the "Count Partitions with Given Difference" problem.

Think of the array divided into two groups:

• Group S1: All numbers with a + sign.
• Group S2: All numbers with a - sign.

We know two things must be true:

1. S1 - S2 = target (This is the requirement of the problem).
2. S1 + S2 = totalSum (The sum of all numbers in both groups equals the total sum of the array).

If we subtract the first equation from the second, we get: 2 * S2 = totalSum - target S2 = (totalSum - target) / 2

This reveals a massive shortcut: we don't need to track + and - signs at all. We just need to find how many subsets (S2) in the array add up exactly to (totalSum - target) / 2.

Algorithm

1. Calculate the totalSum of the array.
2. Check for impossible edge cases:
   • If totalSum - target < 0, the target is too large to reach. Return 0.
   • If (totalSum - target) is an odd number, we can't divide it evenly into two integer partitions. Return 0.
3. Calculate our new target subset sum: (totalSum - target) / 2.
4. Use a standard Top-Down DP (Memoization) approach to count how many subsets equal this new target.
5. Handle the special base case for zeros: If the remaining target is 0 and the current number is 0, return 2. This is because we can either "pick" the 0 or "skip" the 0, and both choices keep our sum at 0.

Code Implementation

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var findTargetSumWays = function (arr, target) {
  function countPartitions(arr, d) {
    const totalSum = arr.reduce((a, b) => a + b, 0);

    // Edge cases: The difference cannot be negative, and must be even
    if (totalSum - d < 0 || (totalSum - d) % 2 !== 0) return 0;

    // This is the subset sum we need to find
    const subsetTarget = (totalSum - d) / 2;
    const n = arr.length;

    // Initialize DP table with -1
    const dp = Array.from({ length: n }, () => Array(subsetTarget + 1).fill(-1));
    const MOD = 1e9 + 7;

    function solve(idx, currentTarget) {
      // Base cases 
      if (idx === 0) {
        // If target is 0 and element is 0, we have 2 choices (pick or skip)
        if (currentTarget === 0 && arr[0] === 0) return 2;
        // If target is 0 (and element is not 0), or element equals target, 1 way
        if (currentTarget === 0 || currentTarget === arr[0]) return 1;
        // Otherwise, 0 ways
        return 0;
      }

      if (dp[idx][currentTarget] !== -1) return dp[idx][currentTarget];

      let notTake = solve(idx - 1, currentTarget);
      
      let take = 0;
      if (arr[idx] <= currentTarget) {
        take = solve(idx - 1, currentTarget - arr[idx]);
      }

      return (dp[idx][currentTarget] = (take + notTake) % MOD);
    }

    return solve(n - 1, subsetTarget);
  }

  return countPartitions(arr, target);
};