494. 目标和（高频题）

494. 目标和

• 解题思路
• 代码

解题思路

这题其实可以转化成动态规划中的零一背包问题，

所以这个背包容量就是 (target + sum(nums)) / 2,要装入背包的东西就是nums[]中的元素。

这其中dp[i]的含义还是背包问题通用的套路：dp[i][j] = x表示，若只在前 i 个物品中选择，若当前背包的容量为 j，则最多有 x 种方法可以恰好装满背包。

注意这个base case可能有点难理解：

1. 如果数组和sum小于目标和S，则不存在正确解，这一点很好理解，所有的数都是正还小于S的话，怎么改变符号也不可能得到目标和；
2. 如果数组和减去目标和的结果sum-S为奇数，同样不存在正确解，因为正号变负号相当于减去两次，所以差值必定为偶数。

代码

class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        int sum = 0;//保存数组的和
        for (int n : nums) {
            sum += n;
        }
        // 这两种情况，不可能存在合法的子集划分
        if (sum < S || (sum + S) % 2 == 1) {
            return 0;
        }
        return subsets(nums, (sum + S) / 2);
    }

    /* 计算 nums 中有几个子集的和为 sum */
    int subsets(int[] nums, int sum) {
        int n = nums.length;
        int[][] dp = new int[n + 1][sum + 1];
        // base case
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= sum; j++) {
                if (j - nums[i - 1] < 0) {
                    // 背包的空间不足，只能选择不装物品 i
                    dp[i][j] = dp[i - 1][j];
                } else {
                    // 两种选择的结果之和
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]];
                }
            }
        }
        return dp[n][sum];
    }
}