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);
    }
}

Q.E.D.


以无限为有限,以无法为有法