Solution 4: Dynamic programming (simplified and optimized)
We can further optimize our solution in several ways.
Firstly, we can trivially conclude that there are 0 ways to attain a target sum if the target sum exceeds the sum of all the values in the array.
Secondly, we can optimize the space complexity of our algorithm by using only a single array --- see my previous post on space-optimizing the dynamic programming solution. This will most likely also improve the runtime of the algorithm, as we don't need to allocate memory to create a new array at each iteration.
But more importantly, we can simplify this problem into a 0--1 Knapsack Problem. Credits to yuxiangmusic who posted this solution in LeetCode's discussion forum --- it's absolutely genius! I'll try to paraphrase his idea here:
The original problem statement is equivalent to: find the number of ways to gather a subset of nums that needs to be positive (P), and the rest negative (N), such that their sum is equal to target.
Therefore...
xxxxxxxxxxsum(P) - sum(N) = target\sum(P) - sum(N) + sum(P) + sum(N) = target + sum(P) + sum(N)2 * sum(P) = target + sum(nums)sum(P) = (target + sum(nums)) / 2