Target Sum
Part of Practice: Prefix & Memo DP
You are given an array of non-negative integers nums and an integer target. Build an expression by writing either + or - in front of every number, then summing them all. Count how many distinct sign assignments make the expression equal target.
Constraints: 1 <= nums.length <= 20, 0 <= nums[i] <= 1000, the total of nums is at most 1000, and -1000 <= target <= 1000.
Examples
- Input:
- nums = [1, 1, 1, 1, 1], target = 3
- Output:
- 5
Make exactly one of the five 1s negative: -1+1+1+1+1 has five placements, each summing to 3.
- Input:
- nums = [1], target = 1
- Output:
- 1
Only +1 works.
- Input:
- nums = [2, 1], target = 2
- Output:
- 0
The four expressions give 3, 1, -1, -3 — never 2.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.