leetcode：494. 目标和

题目

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

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 '+'，在 1 之前添加 '-'，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例：

  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
  1. 输入：nums = [1], target = 1
  2. 输出：1

解答 & 代码

解法一：递归回溯

  1. class Solution {
  2. private:
  3.     int result = 0;
  4.     void backTrack(vector<int>& nums, int start, int target)
  5.     {
  6.         if(start == nums.size())
  7.         {
  8.             if(target == 0)
  9.                 result += 1;
  10.             return;
  11.         }
  13.         // 对当前数 nums[target] 取 +
  14.         backTrack(nums, start + 1, target - nums[start]);
  15.         // 对当前数 nums[target] 取 -
  16.         backTrack(nums, start + 1, target + nums[start]);
  17.     }
  18. public:
  19.     int findTargetSumWays(vector<int>& nums, int target) {
  20.         backTrack(nums, 0, target);
  21.         return result;
  22.     }
  23. };

复杂度分析：设整数数组 nums 长为 N

  • 时间复杂度[中等] 494. 目标和 - 图1：N 个数，每个数可以去 + or -，因此状态数一共有 [中等] 494. 目标和 - 图2
  • 空间复杂度 O(N)：递归栈深度

执行结果：

  1. 执行结果：通过
  3. 执行用时：1172 ms, 在所有 C++ 提交中击败了 24.12% 的用户
  4. 内存消耗：8.8 MB, 在所有 C++ 提交中击败了 71.69% 的用户

解法二：01 背包问题

[中等] 494. 目标和