目标和（超级妙的背包问题）

494. 目标和

给你一个非负整数数组

nums

和一个整数

target

。

向数组中的每个整数前添加

'+'

或

'-'

，然后串联起所有整数，可以构造一个 表达式 ：

• 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于

target

的不同 表达式 的数目。

示例 1：

**输入：**nums = [1,1,1,1,1], target = 3
**输出：**5
**解释：**一共有 5 种方法让最终目标和为 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 + 1 + 1 + 1 - 1 = 3

示例 2：

**输入：**nums = [1], target = 1
**输出：**1

提示：

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 1000
• 0 <= sum(nums[i]) <= 1000
• -1000 <= target <= 1000

想了好一会才找到思路，转换一下题目就是找到两个子数组，和分别为 sum 和 sum + target，这样就可以抵消了

classSolution{public:intfindTargetSumWays(vector<int>& nums,int target){int sum =0;for(auto u : nums){
            sum += u;}int a = sum - target;if(a &1)return0;if(a <0)return0;int bag = a /2;
        vector<int>dp(bag +1,0);
        dp[0]=1;for(auto u : nums){for(int j = bag; j >= u; j--){
                dp[j]+= dp[j - u];}}return dp[bag];}};