mediumDynamic programming, 1D target 25 min
Signs to a target
You get a list of non-negative integers nums and an integer target. Put a plus or a minus sign in front of every number, then add them all up. Return how many of the sign choices give exactly target.
Two choices are different when at least one position has a different sign, even if the numbers are equal. That includes 0: +0 and -0 at the same position are two different choices.
Example 1
Input
nums = [1, 2, 1], target = 2Output2+1 + 2 - 1 = 2 and -1 + 2 + 1 = 2. The other six choices give 4, 0, -2, 0, -2 and -4.
Example 2
Input
nums = [3], target = 1Output0+3 is 3 and -3 is -3.
Example 3
Input
nums = [0, 2], target = 2Output2+0 + 2 and -0 + 2 both make 2, and they count as two choices.
Constraints
1 ≤ len(nums) ≤ 100
0 ≤ nums[i] ≤ 1,000
0 ≤ sum(nums) ≤ 1,000
-1,000 ≤ target ≤ 1,000
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.
Run examples checks the examples. Submit runs every test, including edge cases and, when the problem has one, a speed check on a large input.