Target Sum

发表于 | 分类于

给出非负的整数数组a1…an，和一个目标数target。对数组中的每一个数，都可以选择+或者-。找出有多少种+／-的组合方法可以得到目标数target。

考虑到sum(P) - sum(N) = target（sum(P)是符号为正的数的和，sum(N)是符号为负的数的和），可以得出sum(P) = sum(N) + target，即2 * sum(P) = target + sum(N) + sum(p) = target + sum。将问题转化为求符号为正的数的和为target + sum的组合的个数。

算法如下: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public int findTargetSumWays(int[] nums, int s) {
        int sum = 0;
        for (int n : nums)
            sum += n;
        return sum < s || (s + sum) % 2 > 0 ? 0 : subsetSum(nums, (s + sum) >>> 1); 
    }   
	/**
	 * 这个函数是采用迭代的方式计算数组中和为s的个数
	 */
    public int subsetSum(int[] nums, int s) {
        int[] dp = new int[s + 1]; 
        dp[0] = 1;
        for (int n : nums)
            for (int i = s; i >= n; i--)
                dp[i] += dp[i - n]; 
        return dp[s];
    }
}