385. Target Sum
Your function receives an array of non-negative integers nums and an integer target.
You must place a sign — either + or - — in front of every element, then evaluate the resulting expression. For example, from nums = [2, 1] you can build +2+1, +2-1, -2+1, and -2-1.
Return how many distinct sign assignments make the expression evaluate to exactly target. Two assignments are distinct if any element receives a different sign, even when the elements have equal values.
Example 1:
Input: nums = [1, 1, 1, 1, 1], target = 3
Output: 5
Explanation: Any expression with exactly one minus sign sums to 3 (for example -1+1+1+1+1), and there are five positions the minus can occupy.
Example 2:
Input: nums = [1], target = 1
Output: 1
Explanation: Only +1 works; -1 evaluates to -1.
Constraints:
- 1 ≤ nums.length ≤ 20
- 0 ≤ nums[i] ≤ 1000
- 0 ≤ sum(nums) ≤ 1000
- -1000 ≤ target ≤ 1000
Hints:
Each element takes one of two signs, so there are 2^n expressions. With n <= 20 a plain recursion over "index, running sum" already finishes — but there is a reframing that collapses the problem entirely.
Split the elements into P (got +) and M (got -). Then sum(P) - sum(M) = target and sum(P) + sum(M) = total, so sum(P) = (total + target) / 2 — a fixed number. If that value is negative or fractional the answer is 0; otherwise count subsets of nums with that sum (0/1-knapsack counting: one dp array, capacity iterated downward).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [1, 1, 1, 1, 1], target = 3
Expected output: 5