Target Sum
Problem
You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.
Find out how many ways to assign symbols to make sum of integers equal to target S.
Example 1:
Input: nums is [1, 1, 1, 1, 1], S is 3.
Output: 5
Explanation:
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
There are 5 ways to assign symbols to make the sum of nums be target 3.
Note:
- The length of the given array is positive and will not exceed 20.
- The sum of elements in the given array will not exceed 1000.
- Your output answer is guaranteed to be fitted in a 32-bit integer.
Solution
Convert to Subproblem: Find Subset with Sum n
public class Solution {
public int findTargetSumWays(int[] nums, int S) {
int sum = 0;
for (int num : nums) sum += num;
if (sum < S || (sum + S) % 2 == 1) return 0;
return subset(nums, (sum + S) / 2);
}
private int subset(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
for (int num : nums) {
for (int i = target; i >= num; i--) {
dp[i] += dp[i - num];
}
}
return dp[target];
}
}
Analysis
We try to convert this problem to finding subset with sum target
Let's say we have sum(+)
with all positive number and sum(-)
with all negative numbersum(+) - sum(-) = S
=> sum(+) - sum(-) + sum(+) + sum(-) = S + sum(+) + sum(-)
2 * sum(+) = sum + S
=> sum(+) = (sum + S) / 2
Hence our target is (sum + S) / 2
To get how many ways, we need to find how many subsets we can construct with target
We use the idea in Partition Equal Subset Sum