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) =
5target (int) =
3Returns (int)
5Example 2
Input
nums (int[]) =
[1]size (int) =
1target (int) =
1Returns (int)
1Example 3
Input
nums (int[]) =
[1,2,1]size (int) =
3target (int) =
0Returns (int)
2This 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 0Ready to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run