一、题目内容 中等

给你一个整数数组 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

    二、解题思路

    看到这道题，应该有一种直觉，回溯法暴力搜出来，确实可以但超时。

这道题目咋眼一看和动态规划背包啥的也没啥关系。本题要如何使表达式结果为 target，
有加有减，加的元素组成一组，减的元素组成一组，又变成两组整体集合 A、B。

由于加减法，符合交换律和结合律，所以可以分成两组整体集合。

这就又像之前 6、7 题了。假设 A 是加的元素集合，和为 left，B 是减的元素集合，和为 right。
则有 sum = left + right，target = left - right。
题目给了 nums、target，就是已知 sum、target，求 A 集合有几种？

一个集合确定了，另一个也就确定了。

sum + target = 2 left，所以 left = (sum + target) / 2，即背包最大容量为 left，

  • 如果 left 不是整数，说明不存在这种 A 集合，直接返回 0
  • 如果 left 小于 0，也说明不存在这种 A 集合，直接返回 0
  • 如果 left > sum，也不存在这种 A 集合，直接返回 0 :::warning 这次和之前遇到的背包问题不一样了，之前都是求容量为j的背包，最多能装多少。
    本题则是装满有几种方法。其实这就是一个组合问题了。 ::: 根据动规五部曲
  1. 确定dp数组以及下标的含义

01背包中，dp[j] 表示： 容量为 j 的背包，所背的物品价值可以最大为 dp[j]。
套到本题，dp[j] 表示 背包总容量是 j，可以填满 j 总共有 dp[j] 种方法。

  1. 确定递推公式

那么只要搞到nums[i]的话，凑成dp[j]就有dp[j - nums[i]] 种方法。
例如：dp[j]，j 为5，

  • 已经有一个1（nums[i]） 的话，有 dp[4]种方法 凑成 dp[5]。
  • 已经有一个2（nums[i]） 的话，有 dp[3]种方法 凑成 dp[5]。
  • 已经有一个3（nums[i]） 的话，有 dp[2]中方法 凑成 dp[5]
  • 已经有一个4（nums[i]） 的话，有 dp[1]中方法 凑成 dp[5]
  • 已经有一个5 （nums[i]）的话，有 dp[0]中方法 凑成 dp[5]

那么凑整dp[5]有多少方法呢，也就是把 所有的 dp[j - nums[i]] 累加起来。

  1. dp[j] += dp[j - nums[i]]

:::info 这个公式在后面在讲解背包解决排列组合问题的时候还会用到！ :::

  1. dp 数组如何初始化

从递归公式可以看出，在初始化的时候 dp[0] 一定要初始化为 1，dp[0] = 1，理论上也很好解释，装满容量为0的背包，有 1 种方法，就是装 0 件物品。

  1. 确定遍历顺序

先物品，再背包

三、具体代码

  1. /**
  2.  * @param {number[]} nums
  3.  * @param {number} target
  4.  * @return {number}
  5.  */
  6. var findTargetSumWays = function (nums, target) {
  7.   const sum = nums.reduce((pre, cur) => pre + cur, 0)
  8.   if ((sum + target) % 2) return 0
  9.   const left = (sum + target) / 2
  10.   if (left > sum || left < 0) return 0
  11.   // 初始化
  12.   const dp = new Array(left + 1).fill(0)
  13.   dp[0] = 1
  15.   for (let i = 0; i < nums.length; i++) {
  16.     for (let j = left; j >= 0; j--) { 
  17.       dp[j] += (dp[j - nums[i]] || 0)
  18.     }
  19.   }
  21.   return dp[left]
  22. };

四、其他解法