LeetCode #494：Target Sum(目标和)

题目描述

乍一看本题和背包问题没关系，但也能转换成 01 背包问题进行求解。另外，不同于 #416 运用 01 背包求最多能装多少东西，本题是运用 01 背包解决排列组合问题，其递推公式略有不同。

按照题意，我们设 nums 数组中，所有添加正号的数和为 positiveSum、所有添加负号的数和为 negativeSum，显然有：

positiveSum - negativeSum = target
positiveSum + negativeSum = sum // sum为数组nums中所有数之和

上述两式中，我们消去 negativeSum，可得 positiveSum = (sum + target) / 2。由于 sum 和 target 对于一组数据来说是固定量，于是原问题就转化为：在数组 nums 中取若干个数，使得它们的和等于 positiveSum，有多少种不同取法（即装满容量为 positiveSum 的背包有多少种装法）？

之前都是求容量为 j 的背包，最多能装多少东西；而本题则是装满有几种方法，这就变成了 “组合” 问题。其递推公式为：

dp[j] = dp[j] + dp[j - nums[i]] // 不装物品i的情况加上装物品i的情况

完整代码实现如下。

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int n = nums.size();
        int sum = 0;
        for(int i = 0; i < n; i ++)
            sum += nums[i];
        
        if((target + sum) % 2 == 1) // 当target+sum为奇数时，无解，例如target=3、sum=4
            return 0;
        
        if(abs(target) > sum) // 当目标值的绝对值比sum还大，肯定无解
            return 0;
        
        int v = (target + sum) / 2;
        vector<int> dp(v + 1, 0);
        dp[0] = 1; // dp数组第0项初始化1，代表装满容量为0的背包只有一种方法（不装任何东西）
        for(int i = 0; i < n; i ++) {
            for(int j = v; j >= nums[i]; j --) {
                dp[j] = dp[j] + dp[j - nums[i]];
            }
        }

        return dp[v];
    }
};