Target Sum
You're given an array nums of non-negative integers and an integer target. Put a + or a - sign in front of every number, then evaluate the resulting expression. Return how many different sign assignments make the expression equal target. Two assignments differ if any position gets a different sign, so each 0 doubles the count (+0 and -0 are separate choices).
Examples
nums = [1,1,1,1,1], target = 3 returns 5
Four numbers take + and one takes -, and that single - can go on any of the five positions, for example -1 + 1 + 1 + 1 + 1 = 3. That gives 5 ways.
nums = [1], target = 1 returns 1
+1 = 1 is the only way; -1 gives -1.
nums = [0,0,1], target = 1 returns 4
The 1 must be positive, and each 0 can take either sign without changing the total, so there are 2 * 2 = 4 assignments.
Constraints
- 1 <= nums.length <= 20
- 0 <= nums[i] <= 1000
- -1000 <= target <= 1000
Hints
Assigning + or - to each number partitions them into two groups, can you express the target as a sum over one group?
Reduce to a subset-sum count: find subsets summing to (total + target) / 2.
Let S = sum(nums). If (S + target) is odd or |target| > S, return 0. Let need = (S + target) / 2. Run 0/1 knapsack counting: dp[0] = 1, then for each num, iterate j from need down to num and add dp[j] += dp[j - num]. Return dp[need].
Drill This: Your Approach First
Approach
Let P be the sum of the numbers given +, and N the sum of those given -. Then P - N = target and P + N = total, so P = (total + target) / 2, and the question becomes how many subsets sum to P. If total + target is odd or |target| > total, the answer is 0. Otherwise dp[s] counts subsets reaching s, with dp[0] = 1, and for each n you sweep s from P down to n adding dp[s - n]. O(n * P) time, O(P) space.
Time
O(n * P)
Space
O(P)
Pitfall
Solutions
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum = 0;
for (int n : nums) sum += n;
if ((sum + target) % 2 != 0 || Math.abs(target) > sum) return 0;
int p = (sum + target) / 2;
int[] dp = new int[p + 1];
dp[0] = 1;
for (int n : nums) {
for (int s = p; s >= n; s--) {
dp[s] += dp[s - n];
}
}
return dp[p];
}
}class Solution:
def findTargetSumWays(self, nums, target: int) -> int:
total = sum(nums)
if (total + target) % 2 or abs(target) > total:
return 0
p = (total + target) // 2
dp = [0] * (p + 1)
dp[0] = 1
for n in nums:
for s in range(p, n - 1, -1):
dp[s] += dp[s - n]
return dp[p]