Target Sum
Medium· 0/1 knapsack· counting
Problem
Place a + or - sign in front of every number in an array, then evaluate the expression. Count how many sign assignments produce exactly the given target.
Examples
Input: nums = [1,1,1,1,1], target = 3
Output: 5
Exactly one of the five 1s must be negative.
Input: nums = [1], target = 1
Output: 1
Constraints
- • 1 <= nums.length <= 20
- • 0 <= nums[i] <= 1000
- • -1000 <= target <= 1000
Hints & approach
Hint 1
Split the numbers into a positive group P and a negative group N.
Hint 2
P - N = target and P + N = total, so P = (total + target) / 2.
Hint 3
Count subsets summing to P with a 0/1 knapsack counting DP.
Approachtry the hints first
Algebra turns this into counting subsets: the positive group must sum to P = (total + target) / 2, which must be a non-negative integer or the answer is 0. Let cnt[s] be the number of subsets summing to s, with cnt[0] = 1. For each number x, iterate s downward from P to x adding cnt[s-x] into cnt[s]. Zeros are handled naturally because each doubles the count. Return cnt[P].
Time O(n·sum) · Space O(sum)