题目描述:
给定一个非负整数的序列,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];
}
}