Math Dynamic Programming
Proficient Level

Implement the targetSumWaysCount method that counts expressions that reach a target by assigning plus or minus signs.

You are given an array of non-negative integers and a target value. Before every number, you may place either a plus sign or a minus sign.

Return how many different sign assignments produce the target sum. The order of numbers must remain the same; only the signs can change.

Example 1
Input:
nums (int[]) = [1,1,1,1,1]
size (int) = 5
target (int) = 3
Return:
(int) 5
Example 2
Input:
nums (int[]) = [1]
size (int) = 1
target (int) = 1
Return:
(int) 1
Example 3
Input:
nums (int[]) = [1,2,1]
size (int) = 3
target (int) = 0
Return:
(int) 2

This problem can be solved using dynamic programming over possible sums.

Start with one way to make sum 0. For each number, create a new map of sums. Every previous sum can produce two new sums: one by adding the current number and one by subtracting it. After all numbers are processed, the count stored for the target is the answer.

This avoids generating every expression as a string and focuses only on reachable sum counts.

Pseudocode:

function targetSumWaysCount(nums, size, target):
    ways = map with 0 -> 1
    for each number in nums:
        nextWays = empty map
        for each sum and count in ways:
            nextWays[sum + number] += count
            nextWays[sum - number] += count
        ways = nextWays
    return ways[target] if target exists else 0
Run your code to see the result.