Target Sum
MediumDynamic Programming
You are given an integer array nums and an integer target. Put either a + or a - sign in front of every element of nums (keeping the elements in their given order) and evaluate the resulting expression.
Return the number of different sign assignments whose value equals target. Two assignments are different if at least one position gets a different sign, so each 0 in nums doubles the count (+0 and -0 are separate choices). Return 0 if no assignment works.
Example 1
- Input:
- nums = [1, 2, 3, 4], target = 4
- Output:
- 2
- Explanation
-1 - 2 + 3 + 4and+1 + 2 - 3 + 4both equal 4, and none of the other 14 assignments does.
Example 2
- Input:
- nums = [0, 0, 5], target = -5
- Output:
- 4
- Explanation
- The
5must get a minus sign. Each0can independently be+0or-0without changing the value, giving 2 * 2 = 4 assignments.
Example 3
- Input:
- nums = [2, 3], target = 4
- Output:
- 0
- Explanation
- The only possible values are 5, 1, -1 and -5, so 4 cannot be reached.
Constraints
1 <= nums.length <= 200 <= nums[i] <= 10000 <= sum(nums) <= 1000-1000 <= target <= 1000