Target Sum:目标和的个数

题目描述：
给定一个非负整数的序列，a1，a2，…，an，和目标值s。现在你有2个符号+和-。对于每个整数，您可以选择+或者-作为它的新符号。
找出所有分配符号的方法，以使整数和等于目标值s。

输入: 整型数组nums,比如 [1, 1, 1, 1, 1], 目标值s，如3。
输出: 5
解释:
-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

分析：
给定数组 [1, 2, 3, 4, 5] 和目标和target为3，一种可能的情况是+1-2+3-4+5 = 3
整数子集为 P = [1, 3, 5] ，负数子集为 N = [2, 4]。
原问题可以转换为:
sum(P) - sum(N) = target
sum(P) + sum(N) = 原数组和
2 * sum(P) = target + 原数组和
sum(P)=(target + 原数组和)/2

代码（采用动态规划）：

class Solution {
    public int findTargetSumWays(int[] nums, int s) {
        int total=0;
        for(int i=0;i<nums.length;i++){
            total+=nums[i];
        }
        int target=(s+total)>>>1;
        return total<target || (s+total)%2>0 ? 0 : getCount(nums,target);        
    }
    
    public int getCount(int[] nums,int target){
        int[] dp=new int[target+1];
        dp[0]=1;
        for(int i=0;i<nums.length;i++){
            for(int j=target;j>=nums[i];j--){
                dp[j]+=dp[j-nums[i]];
            }
        }
        return dp[target];
    }
}