目标和

题目

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

思路+代码

思路

本题可以采用回溯、动态规划方法分别完成目标和解算

1. 回溯：

• 数组 nums 的每个元素都可以添加符号 + 或 -，因此每个元素有 2 种添加符号的方法，n 个数对应 $2^n$ 种不同的表达式
• 如果表达式的结果等于目标数 target，则该表达式即为符合要求的表达式
• 可以使用回溯的方法遍历所有的表达式，回溯过程中维护一个计数器 count，当遇到一种表达式的结果等于目标数 target 时，将 count 的值加 1

采用队列的BFS方法也可以遍历所有的表达式，但是这种方式有入队出队操作，在LeetCode提交会超时

2. 动态规划

• 记数组的元素和为 sum，添加 - 号的元素之和为 neg，则其余添加 + 的元素之和为 sum - neg，得到的表达式的结果为:(sum − neg) − neg = sum − 2 * neg = target，即：neg = (sum − target) / 2
• 上式成立的前提是 sum - target 是非负偶数。若不符合该条件可直接返回 0
• 上式成立，问题转化成在数组 nums 中选取若干元素，使得这些元素之和等于 neg，计算选取元素的方案数
  • 定义二维数组 dp，其中 dp[i][j] 表示在数组 nums 的前 i 个数中选取元素，使得这些元素之和等于 j 的方案数。假设数组 nums 的长度为 n，则最终答案为 dp[n][neg]
  • 当没有任何元素可以选取时，元素和只能是 0，对应的方案数是 1，因此动态规划的边界条件是：
    $$dp\lbrack0\rbrack\lbrack j\rbrack=\left\{\begin{array}{l}1,\;j=0\\0,\;j\geq1\end{array}\right.$$
• 当 1 ≤ i ≤n 时，对于数组 nums 中的第 i 个元素 num（i 的计数从 1 开始），遍历 0 ≤ j≤ neg，计算 dp[i][j] 的值
  • 如果 j < num，则不能选 num，此时有 dp[i−1][j]；
  • 如果 j ≥ num，则如果不选 num，方案数是 dp[i−1][j]，如果选 num，方案数是 dp[i−1][j−num]，此时有 dp[i][j]=dp[i−1][j]+dp[i−1][j−num]

因此状态转移方程如下：
$$dp\lbrack i\rbrack\lbrack j\rbrack=\left\{\begin{array}{l}d\lbrack i-1\rbrack\lbrack j\rbrack,\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;j<num\lbrack i\rbrack\\d\lbrack i-1\rbrack\lbrack j\rbrack+d\lbrack i-1\rbrack\lbrack j-num\lbrack i\rbrack\rbrack,\;j\geq num\lbrack i\rbrack\end{array}\right.$$
最终得到 dp[n][neg] 的值即为答案

代码实现

• 回溯：

  class Solution {
  public:
      
      void dfs(vector<int>& nums, int target, int index, int sum, int& count)
      {
          if (index == nums.size())
          {
              if (sum == target)
                  count++;
          }
          else
          {
              dfs(nums, target, index+1, sum+nums[index], count);
              dfs(nums, target, index+1, sum-nums[index], count);
          }
      }
      
      int findTargetSumWays(vector<int>& nums, int target) {
          
          int count = 0;
          dfs(nums, target, 0, 0, count);
          return count; 
      }
  };

• 动态规划：

  class Solution {
      public int findTargetSumWays(int[] nums, int target) {
          int sum = 0;
          for (int num : nums) {
              sum += num;
          }
          int diff = sum - target;
          if (diff < 0 || diff % 2 != 0) {
              return 0;
          }
          int n = nums.length, neg = diff / 2;
          int[][] dp = new int[n + 1][neg + 1];
          dp[0][0] = 1;
          for (int i = 1; i <= n; i++) {
              int num = nums[i - 1];
              for (int j = 0; j <= neg; j++) {
                  dp[i][j] = dp[i - 1][j];
                  if (j >= num) {
                      dp[i][j] += dp[i - 1][j - num];
                  }
              }
          }
          return dp[n][neg];
      }
  }

由于 dp 的每一行的计算只和上一行有关，因此可以使用滚动数组的方式，去掉 dp 的第一个维度，将空间复杂度优化到 O(neg)
实现时，内层循环需采用倒序遍历的方式，这种方式保证转移来的是 dp[i−1][] 中的元素值

• 动态规划（优化空间复杂度）：

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

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/queue-stack/ga4o2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。