题目描述
给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 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
一共有5种方法让最终目标和为3。
说明：
- 数组非空，且长度不会超过 20 。
- 初始的数组的和不会超过 1000 。
- 保证返回的最终结果能被 32 位整数存下。
题目链接： https://leetcode-cn.com/problems/target-sum/
思路
假设我们将数组分为两部分，两部分的和分别为 x，y，数组中所有元素的和为 sum，则有 x + y = sum, x - y = S，可得 x = (sum + S) / 2. 所以，问题就变为了数组能否分为两部分，其中一部分的和为 (sum + S) / 2。可以使用和等和子集一样的方法来做。
- 状态定义：dp[i][j] 表示下标范围为 [0, i] 内数组元素中和为 j 的个数；
- 状态转移：对于第 i 个数，可以选也可以不选，所以 dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]]；
- 边界条件：dp[i][0] = 1，含义是范围 [0, i] 内元素和为 0 的个数为 1，也就是所有的数都不选；dp[0][nums[0]] += 1 if nums[0]<=x，本来 dp[0][0] = 1，如果 nums[0] = 0，此时 dp[0][0] 就等于 2 了，也就可以选择 nums[0]，也可以不选择 nums[0]，因为 nums[0] = 0，所以这两种方法是一样的。
代码如下：
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
if(nums.empty() && S>0) return 0;
int s = 0;
for(int i=0; i<nums.size(); i++){
s += nums[i];
}
if(s<S) return 0;
s += S;
if(s%2!=0) return 0;
int target = s / 2;
vector<vector<int>> dp(nums.size(), vector<int>(target+1, 0));
for(int i=0; i<nums.size(); i++) dp[i][0] = 1; // 边界条件
/*if(nums[0]<=target) dp[0][nums[0]] = 1;
if(nums[0]==0) dp[0][nums[0]] = 2;*/
if(nums[0]<=target) dp[0][nums[0]] += 1; // 这种写法和上面注释的写法是一样的
for(int i=1; i<nums.size(); i++){
for(int j=0; j<=target; j++){
dp[i][j] = dp[i-1][j];
if(j>=nums[i]){
dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]];
}
}
}
return dp[nums.size()-1][target];
}
};
空间复杂度优化：
使用和等和子集一样的方法对空间复杂度进行优化：
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
if(nums.empty() && S>0) return 0;
int s = 0;
for(int i=0; i<nums.size(); i++){
s += nums[i];
}
if(s<S) return 0;
s += S;
if(s%2!=0) return 0;
int target = s / 2;
vector<int> dp(target+1, 0);
dp[0] = 1;
if(nums[0]<=target) dp[nums[0]] += 1;
for(int i=1; i<nums.size(); i++){
for(int j=target; j>=nums[i]; j--){
dp[j] += dp[j-nums[i]];
}
}
return dp[target];
}
};