难度中等419
给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从
或 -中选择一个符号添加在前面。返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
示例：
输入：nums: [1, 1, 1, 1, 1], S: 3 输出：5 解释： -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 //将这组数看成两部分，P->正号 N->负号 //sum(p) - sum(n) = target //sum(p) + sum(n) + sum(p) - sum(n) = target + sum(p) + sum(n) // 2 * sum(p) = target + sum (nums) // 2 * sum(p) = s + sum(nums) // sum(p) = (s+nums) / 2 // 时间复杂度O(N^2) 空间复杂度为O(1) public int findTargetSumWays(int[] nums, int S) { int sum = computeArraySum(nums); if (sum < S || (sum+S) %2 == 1) { return 0; } int w = (sum + S) /2; int [] dp = new int [w+1]; dp[0] = 1; for (int num : nums) { for (int i = w; i>= num;i--) { dp[i] = dp[i]+dp[i-num]; } } return dp[w]; } private int computeArraySum(int [] nums) { int sum = 0; for (int num : nums) { sum+= num; } return sum; }