题目

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

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

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

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

示例 1：

  1. 输入：nums = [1,1,1,1,1], target = 3
  2. 输出：5
  3. 解释：一共有 5 种方法让最终目标和为 3 。
  4. -1 + 1 + 1 + 1 + 1 = 3
  5. +1 - 1 + 1 + 1 + 1 = 3
  6. +1 + 1 - 1 + 1 + 1 = 3
  7. +1 + 1 + 1 - 1 + 1 = 3
  8. +1 + 1 + 1 + 1 - 1 = 3

示例 2：

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

提示：

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

    解题方法

    动态规划

    题目将数组分为left和right两部分，则有如下关系：
    494. 目标和 - 图1
    所以问题转化为求解和为left的不同组合数目。
    494. 目标和 - 图2
    设定动态数组dp[i]表示下标[0, i]中所有数字能够组成和为i的不同组合数。则有如下递推关系：
    494. 目标和 - 图3
    时间复杂度O(mn)，空间复杂度O(n)（m为数组中数字个数，n为left大小）。
    C++代码：
    1. class Solution {
    2. public:
    3.   int findTargetSumWays(vector<int>& nums, int target) {
    4.       int sum = 0;
    5.       for(int num : nums)     sum += num;
    6.       if((sum+target)%2)      return 0;
    7.       if(abs(target) > sum)   return 0;
    8.       int left = (sum+target)/2;
    9.       vector<int> dp(left+1, 0);
    10.       dp[0] = 1;
    11.       int result = 0;
    12.       for(int i=0; i<nums.size(); i++) {
    13.           for(int j=left; j>=nums[i]; j--)    dp[j] += dp[j-nums[i]];
    14.       }
    15.       return dp[left];
    16.   }
    17. };

    递归回溯

    递归回溯穷举所有可能
    时间复杂度O(2^n)，空间复杂度O(n)
    C++代码： ```cpp class Solution { private: int result = 0;

public: void dfs(vector& nums, int target, int idx) { if(idx==nums.size()) { if(target==0) result++; return; } dfs(nums, target-nums[idx], idx+1); dfs(nums, target+nums[idx], idx+1); }

  1. int findTargetSumWays(vector<int>& nums, int target) {
  2.     dfs(nums, target, 0);
  3.     return result;
  4. }

}; ```