Leetcode 494.目标和

题目描述：

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

• 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

1
2
3
4
5
6
7
8

输入：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：

1
2

输入：nums = [1], target = 1
输出：1

提示：

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 1000
• 0 <= sum(nums[i]) <= 1000
• -1000 <= target <= 1000

链接：

https://leetcode-cn.com/problems/target-sum

题目分析

  对于每一个整数，要不添加的是正号，要不添加的是负号，那么可以将他们分成两类。假设正数类的和为 pos，负数类的和为 neg，那么需要满足 pos - neg = target。而我们有 pos + neg = sum（sum 表示数组所有数的和）。那么可以联立得到 neg = (sum - target) / 2。那这个问题就转化成了：在 nums 中挑选若干个数使得它们的和为 neg。是不是有点熟悉？其实和 Leetcode 416.分割等和子集 的解法一样了。不过那道题是判断目标和是否存在，而这道题是需要输出目标和的数量。
  采取同样的动态规划方法，外层是逐一判断每个数放入和不放入背包的情况，内层是计算凑成某个背包大小的方案数。这个时候我们要把 dp[0] 初始化为 1，表示一种方案的起始点。同样的，使用空间降维的方法，内层循环需要从大到小。
  这道题也可以先进行一些剪枝，比如我们从提示中可以看到数组中的数是正整数，那么计算得到的 neg 不能小于 0，还有 diff 也不能是奇数，遇到这两种情况都可以直接返回 0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for(const int& num : nums){
            sum += num;
        }
        int diff = sum - target;
        if(diff < 0 || (diff & 1) != 0) return 0;
        int neg = diff >> 1;
        vector<int> dp(neg+1, 0);
        dp[0] = 1;
        for(const int& num : nums){
            for(int j = neg; j >= num; j--){
                dp[j] += dp[j - num];
            }
        }
        return dp[neg];
    }
};

  时间复杂度：$O(n\times(sum - target))$，其中 $n$ 是数组的元素个数，$sum$ 是数组元素和，$target$ 是目标和。也就是我们双层遍历的时间复杂度。
  空间复杂度：$O(sum-target)$，其中 $sum$ 是数组元素和，$target$ 是目标和。也就是保存动态规划状态的数组大小。