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

算法思路：

首先根据提示可知 nums[i] 可能为 0 ，而 对0 加减不影响和，但影响方法总数， 对于每个 0，都可以 + 和 - ，所以先统计出 0 的个数（c0），并且去 0 （放到一个 list 中）。设 A：对应加法的数之和 ，B: 对应减法的数之和 ，则 sum = A+B，target = A-B，所以 sum + target = 2A 一定是非负的偶数，且 A = (sum + target) /2。
此时问题就转化为，装满容量为 A 的背包，有几种方法，即 01背包问题，对于每个数考虑选与不选的情况，dp[j] 表示 所选数的和为 j 的方法数，且是⼀个组合问题。算出装满容量为 A（对应加法） 的背包的方法种数后，对应减法也就确定了，所以最后只要乘上 只考虑 0 的方法总数（2的 c0 次方）就可以了。

递推公式为： dp[j] += dp[j - nums[i]]，若考虑选数 num[i] ，则所选数 和为 j 的方法种数 也即 和为 j-num[i] 的方法种数，再累加起来。

代码实现：

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0, c0 = 0;
        List<Integer> list = new LinkedList<>();
        // 统计 0 的个数，并且去 0 放到 list 中
        for (int num : nums) {
            if (num == 0) {
                c0++;
            } else {
                sum += num;
                list.add(num);
            }
        }
        // 设 A：对应加法的和   B: 对应减法的和 则 sum = A+B,target = A-B
        // 所以 sum + target = 2A 一定是非负的偶数，且 A = (sum + target) /2
        if (sum + target < 0 || (sum + target) % 2 == 1) return 0;
        int bagSize = (target + sum) / 2;
        // dp[j]: 所选数的和为 j 的方法种数
        int[] dp = new int[bagSize + 1];
        // 初始为 1，即啥都不选
        dp[0] = 1;
        for (int num : list) {
            for (int j = bagSize; j >= 1; j--) {
                if (j >= num) {
                    // 和为 j 的方法种数 也即 和为 j-num 的方法种数，再累加起来
                    dp[j] += dp[j - num];
                }
            }
        }
        // 对于每个 0，都可以 + 和 - 
        return dp[bagSize] * (int) Math.pow(2, c0);
    }
}