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

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，这样就可以抵消了

class Solution { public:     int findTargetSumWays(vector<int>& nums, int target) {         int sum = 0;         for (auto u : nums) {             sum += u;         }         int a = sum - target;         if (a & 1) return 0;         if (a < 0) return 0;         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];     } };