You are given non-negative integers nums and an integer target. Put a + or a - in front of every number and evaluate the sum. Count how many of the 2^n sign assignments make the sum equal to target.
Implement find_target_sum_ways(nums: list[int], target: int) -> int.
find_target_sum_ways([2, 1, 1], 2) # 2 +2+1-1, +2-1+1
find_target_sum_ways([0, 3], 3) # 2 +0+3, -0+3 (a zero can take either sign)
find_target_sum_ways([4], -5) # 0
Constraints: 1 <= len(nums) <= 60, 0 <= nums[i] <= 1000, sum(nums) <= 1000, |target| <= 1000.
Enumerating every assignment is 2^n, far too slow at n = 60; aim for O(n × sum(nums)).
Show hint
after the first few numbers only the running sum matters, not the signs that produced it, and there are few possible running sums. (Alternatively: what must the numbers given + add up to?)