Target Sum
Medium · Dynamic Programming · Array · Dynamic Programming · Backtracking
Problem
You are given an integer array nums and an integer target. Build an expression by writing either a + or a - sign in front of every element of nums (keeping the elements in their original order) and then evaluating the result.
Return the number of different sign assignments whose expression evaluates to exactly target. Two assignments are different if at least one position receives a different sign, even when the elements at those positions are equal.
Examples
Input: nums = [2,1,1], target = 2 Output: 2
Both +2+1-1 and +2-1+1 evaluate to 2.
Input: nums = [1,2,3,4], target = 0 Output: 2
-1+2+3-4 and +1-2-3+4 are the only assignments that cancel out to 0.
Input: nums = [5], target = 3 Output: 0
The only reachable values are 5 and -5.
Constraints
- 1 <= len(nums) <= 20
- 0 <= nums[i] <= 1000
- 0 <= sum(nums) <= 1000
- -1000 <= target <= 1000
Approaches
- Try every sign assignment — time O(2^n), space O(n) for the recursion
Follow-up
What if the elements may be negative? The subset sum P can then be negative too, and the reduction still works but the table needs an offset. A dictionary of reachable values to counts, updated per element with v + x and v - x, handles any signs directly in O(n · range).
Related problems
Start free on Cariara · Coding problems · System design studio
