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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/target-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

题目的意思就是将数组划分为两部分，两部分之差为target。

设 ，则 %2F2#card=math&code=a%3D%3D%28sum%2Btarget%29%2F2&id=xqOJe)，要求的就是从选出部分元素和为a的方案数。

就是一个01背包的问题，状态定义和状态转移方程不难想，有一些细节需要注意，写在注释里了。

代码

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int n = nums.length;
        int sum = Arrays.stream(nums).sum();
        // 因为target可能是负数，因此sum + target可能是负数，这时dp数组长度可能为负数了
        // 分析一下，因为sum一定不为负，而target的绝对值一定大于sum，即使全部添加负号也无法凑出target，所以可以返回0
        // 另外，sum + target只能是偶数，如果为奇数，a就应该是带小数的，而数组中全是整数，因此如果是奇数也返回0
        if (sum + target < 0 || (sum + target) % 2 == 1) {
            return 0;
        }
        int k = (sum + target) / 2;
        int[] dp = new int[k + 1];
        // 不单独考虑第一个数，因为那样会变得复杂，需要考虑nums[0]和k的大小关系，见如下代码：
//        if (nums[0] <= k) {
//            // 要特别注意 nums[0]==0 时 dp[0]=2 表示选和不选各一种方案
//            if (nums[0] == 0) {
//                dp[0] = 2;
//            } else {
//                dp[nums[0]] = 1;
//            }
//        }
        // dp[0]=1表示使用0个数，凑出0的方案数为1
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = k; j >= nums[i - 1]; j--) {
                dp[j] += dp[j - nums[i - 1]];
            }
        }
        return dp[k];
    }
}