Leetcode 494. 目标和

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

思路

这一道题感觉也是把数组里面的元素分成两份，然后取他们的差值，求差值等于target的组合数。
即求装满背包的方法数，一般是 dp[j] += dp[j - nums[i]];
先分析一下特别的情况，如果sum是小于 target的绝对值的，namo就不能凑成，直接返回 0 即可
我们把集合分成两份，相加减，令左边的和等于 L 那 右边的和等于 R ，L + R = sum
L - (sum - L) = target 即 L = (sum + target) / 2;
sum 和 target都是已知的，所以我们就可以求出来L 这就是背包的容量

又因为 L 一定是一个整数，所以(sum + target) 一定是一个偶数，如果是奇数，直接return 0即可
dp[i]含义 ：凑成 i 一共有 dp[i] 种方法
递推公式：dp[j] += dp[j - nums[i]];
初始化： dp[0] = 1，当凑成0的时候只有一种方法

代码

class Solution {
    
public:
    // 求装满背包要几种方法 dp[j] += dp[j - nums[i]];
    // 加入 L是正数和 那么就有 R是负数的和，不看符号加起来等于sum
    // 所以 L - (sum - L) = target，sum和target是固定的，所以
    // L = (target + sum) / 2;
    // L就是背包的最大容量
    int findTargetSumWays(vector<int>& nums, int target) {
    
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) sum += nums[i];
        // 如果target大于sum则没有方案
        if (abs(target) > sum) return 0;

        int L = (sum + target) / 2;
        // 因为 L 一定是整数，所以(sum + target) 一定是偶数
        if ((sum + target) & 1) return 0;

        int dp[L + 1]; // dp[i] 凑成和 i 共 dp[i] 种方法
        for (int i = 0; i <= L; i++) dp[i] = 0;
        dp[0] = 1; // 数组初始化，和为 0 共有 1 种方法

        for (int i = 0; i < nums.size(); i++) {
    
            for (int j = L; j >= nums[i]; j--) {
    
                dp[j] += dp[j - nums[i]];
            }
        }

        return dp[L];
    }
};