Target Sum

Problem

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

You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.

For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1".

Return the number of different expressions that you can build, which evaluates to target.

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 of nums be target 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

Constraints:

1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000

Solution

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var findTargetSumWays = function(nums, target) {
    const sum = nums.reduce((acc, cur) => acc + cur, 0);
    const dp = Array(nums.length)
        .fill(null)
        .map(() => Array(sum * 2 + 1).fill(0));

    dp[0][nums[0] + sum] += 1;
    dp[0][-nums[0] + sum] += 1;

    for (let i = 1; i < nums.length; i++) {
        for (let j = -sum; j <= sum; j++) {
            const sumIndex = j + sum;
            dp[i][sumIndex] += dp[i - 1]?.[sumIndex + nums[i]] ?? 0;
            dp[i][sumIndex] += dp[i - 1]?.[sumIndex - nums[i]] ?? 0;
        }
    }

    return dp[nums.length - 1]?.[target + sum] ?? 0;
};

We will implement a DP solution. Let dp[i][j] be the number of ways to add up to j using nums[0:i + 1].

For the base case, if i = 0, then using nums[0:1] there is one way to sum up nums[0:1] and one way to sum up -nums[0:1] (all other sum has 0 ways to be summed up).
For the recursive case, the number of ways to add up to j is the number of ways that adds up to j ± nums[i] (ie. using nums[i] we can add up to j), but not including the current value nums[i] (ie. dp[i - 1][j ± nums[i]]).

Note that in the actual code, since we can't have negative indices, for dp to be in range of [-sum, sum], we shift each index by sum (ie. indices [0, 2 * sum] maps to values [-sum, sum]).

Problem​

Solution​

Problem

Solution