改变一组数的正负号使得它们的和为一给定数
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.
题目描述：
给定一个全为1的数组，和一个目标值，数组中每个元素可正可负，求出可以有多少种组合使得数组的和为目标值。
思路分析：
我们将添加“+”的数放入集合P，其它的数放入集合N，于是我们有：
sum(P) - sum(N) = target
sum(P) + sum(N) = sum
于是有sum(P) = (target + sum) / 2，那么不妨这样理解题意，从一个数组中选定一些数，使它们的和为sum(P)，如此就变成了很经典的0/1背包问题，从一个n大小的背包中选出总和为sum(P)的方案个数。
状态表示：dp[i] [j]代表前i个数中和为j的方案个数。
状态转移方程：dp [i] [j] = dp[i-1] [j] + dp[i-1] [j-nums[i]]，dp [0] [0] = 1
返回结果：dp[n] [target],n为数组大小，target为sum(P)。
代码：
public int findTargetSumWays(int []nums,int S){
int sum=0;
for(int num:nums){
sum=sum+num;
}
int target=(sum+S)/2;
int []dp=new int[target+1];
dp[0]=1;
for(int num:nums){
for(int i=target;i>=num;i--){
dp[i]=dp[i]+dp[i-num];
}
}
return dp[target];
}
DFS解法
public int findTargetSumWays(int[]nums,int S){
return findTargetSumWays(int[]nums,int S);
}
private int findTargetSumWays(int []nums,int start int S){
if(start==nums.length){
return S==0?1:0;
}
return findTargetSumWays(nums,start+1,S-nums[start])+
findTargetSumWays(nums,start+1,S+nums[start]);
}