☆☆☆☆思路：把所有符号为正的数总和设为一个背包的容量，容量为x；把所有符号为负的数总和设为一个背包的容量，容量为y。
令sum为数组的总和，则x+y = sum。而两个背包的差为S,则x-y=S。从而求得x=(S+sum)/2。
因此，题目转换为背包问题：给定一个数组和一个容量为x的背包，求有多少种方式让背包装满。
class Solution { public int findTargetSumWays(int[] nums, int S) { int sum = 0; for (int num : nums) { sum += num; } // 目标和不可能大于总和 if (S > sum) return 0; // 背包容量为整数，sum+S为奇数的话不满足要求 if (((sum + S) & 1) == 1) return 0; int target = (sum + S) / 2; int[] dp = new int[target + 1]; dp[0] = 1; for (int i = 0; i < nums.length; i++) { for (int j = target; j >= nums[i]; j--) { dp[j] += dp[j - nums[i]]; } } return dp[target]; } }
原文：https://www.cnblogs.com/HuangYJ/p/14217160.html