🎯494.目标和

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串联起来得到表达式 “+2-1” 。 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

思路

基本思想

由于需要最终获得target，肯定是一部分数为正一部分数为负，那么我们可以先将target拿出来，剩下的数等分成两半，一半为正一半为负，这样相加抵消肯定为0，对target没有影响

将target拿出来之后剩下的数记为sum-target，其中sum是nums求和得到的，之后将sum-target分成两半得到的数为： $$ capacity=\frac{sum-target}{2} $$ capacity作为背包的容量，然后看nums中有哪些方案可以将背包刚好填满，记录这些方案数即可

现在的问题就是如何记录所有的方案数，dp[j]代表和为j的方案数

• 已经有一个1（nums[i]） 的话，有 dp[4]种方法 凑成 容量为5的背包。
• 已经有一个2（nums[i]） 的话，有 dp[3]种方法 凑成 容量为5的背包。
• 已经有一个3（nums[i]） 的话，有 dp[2]中方法 凑成 容量为5的背包
• 已经有一个4（nums[i]） 的话，有 dp[1]中方法 凑成 容量为5的背包
• 已经有一个5 （nums[i]）的话，有 dp[0]中方法 凑成 容量为5的背包

将上面的情况累加，所以最终的公式为： $$ dp[j] += dp[j - nums[i]] $$ 可以理解为依次向当前背包中放入nums[i]，剩下的dp[j-nums[i]]继续求解方案数，不同的nums[i]形成了不同的方案数，所以需要累加

注意有两种情况问题无解

1. 数组求和都小于target，肯定无法形成target
2. 按照公式1求解的capacity不是整数，数组中的数组合都是整数，不符合要求

相当于找出那些数加负号，剩下的数都加正号，正负抵消之后就形成了最终的target

执行流程

1. 计算背包容量

2. 初始化dp数组，要记住dp数组的含义

   所以dp[0]=1

3. 计算01背包（形成负数的方案数）

4. 返回结果

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum=accumulate(nums.begin(),nums.end(),0);
        //两种情况无解
        if(sum<target||(sum-target)%2!=0)
            return 0;
        int capacity=(sum-target)/2;
        vector<int> dp(capacity+1,0);//除了dp[0],其余的都要递推得来
        dp[0]=1;//形成0的同号数字组合只有一种
        for(int i=0;i<nums.size();++i){
            for(int j=capacity;j>=nums[i];--j){
                dp[j]+=dp[j-nums[i]];
            }
        }
        return dp[capacity];
    }
};

总结

要想形成target，肯定会剩下一部分sum-target，这部分干扰项需要去除，去除的过程中不能对target造成任何影响，所以想到了分成两半，一半正数一半负数，此数作为背包的容量

此时只需要从集合中找出所有的能将背包刚好填满的方案即可

本题中的dp数组含义与之前的不一样，本题中dp[j]代表同号数字组合得到j的所有方案数，所以dp是由前面的方案数累加得到的