思路：本题按照描述应该是可以使用回溯法进行暴力搜索，但是实际上会超时，所以我们使用动态规划01背包问题来解决，本题实质上是前两天题目的变体，实际上题意是问将集合分成两个部分，两个部分的差值为target,求两个部分一共有几种组成方式。
实际上我们只需要求出一个部分的组合方式即可，因为两个部分是两两对应的。所以我们设一个部分为left一个部分为right 则left - right = target ,left + right = sum;那么可以推出 left = (sum + target)/2; 即我们要确定left一共有几种组合方式，我们设dp[j]为装满背包大小为j一共有多少种组合方式，那么求left一共有几种组合方式转换为dp数组就是求dp[left]的值。
递推公式方面 当包里已经有nums[i]的时候 有dp[left - nums[i]]种方法，对于所有的nums[i]都满足这个公式，所以dp[left]是这些结果的累加
class Solution {
public int findTargetSumWays(int[] nums, int target) {
// 本质上是问 分成两堆时， 一堆减去另一堆的差值满足target的情况下有几种分化
int sum = 0;
for (int i: nums) {
sum+=i;
}
// 考虑无解的情况
if (sum < target) return 0;
if ((sum + target)%2 == 1) return 0;
// 找到和为targetSum的组合
int targetSum = (sum + target)/2;
// 根据测试用例 排除为负的情况
if (targetSum < 0) return 0;
// dp[j]表示装满体积为j的包一共有多少种方法
int[] dp = new int[targetSum+1];
// 填满体积为0的包的方法只有一个 就是不放物品
dp[0] = 1;
for (int i = 0; i < nums.length; i++) {
for (int j = targetSum; j >= nums[i] ; j--) {
// 如果包里已经有一个nums[i] 那么 有dp[j-nums[i]种方法得到dp[j]
dp[j] += dp[j - nums[i]];
}
}
return dp[targetSum];
}
}
