题目

给定一个非负整数数组，a1,a2, … , an,和一个目标数，S。现在你有两个符号+ 和 -。对于数组中任意一个整数，你都可以从 + 和 - 中选择一个符号添加在前面。

返回可以使最终数组和为目标数S的所有添加符号的方法数。
image.png

思路

思路一：深度优先搜索策略（回溯法）

  1. class Solution:
  2.     result = 0
  3.     def findTargetSumWays(self, nums: List[int], S: int) -> int:
  4.         if len(nums) == 0: return 0
  5.         self.backtrack(nums, i = 0, S)# i表示第i个元素
  6.         return self.result
  8.     # 回溯法模板
  9.     def backtrack(self, nums, i, rest):
  10.         # i表示第i个元素
  11.         # base case
  12.         if i == len(nums):
  13.             if rest == 0:
  14.                 self.result += 1
  15.             return
  17.         # 给nums[i]选择 - 号
  18.         rest += nums[i]
  19.         # 穷举 nums[i + 1]
  20.         self.backtrack(nums, i +1, rest)
  21.         # 撤销选择
  22.         rest -= nums[i]
  24.         # 给nums[i] 选择 + 号
  25.         rest -= nums[i]
  26.         self.backtrack(nums, i + 1, rest)
  27.         rest += nums[i]

复杂度分析

  • 时间复杂度：O(2^N)，其中 NN 是数组 nums 的长度。
  • 空间复杂度：O(N)，为递归使用的栈空间大小。

更优雅的实现

  1. class Solution:
  2.     count = 0
  3.     def findTargetSumWays(self, nums: List[int], S: int) -> int:
  4.         self.calculate(nums, 0, 0, S)
  5.         return self.count
  7.     def calculate(self, nums, i, Sum, target):
  8.         if i == len(nums):
  9.             if Sum == target:
  10.                 self.count += 1
  11.         else:
  12.             self.calculate(nums, i + 1, Sum + nums[i], target)
  13.             self.calculate(nums, i + 1, Sum - nums[i], target)

思路二：动态规划

还没搞懂
系统学了动态规划再看
这道题是一道常见的背包问题。
状态变量：dp[i][j]：数组中前i个元素，组成和为j的方案数。

转移方程：
dp[i][j] = dp[i - 1][j - nums[i]] + dp[i - 1][j + nums[i]]

  1. class Solution:
  2.     def findTargetSumWays(self, nums: List[int], S: int) -> int:
  3.         if not nums: return 0
  4.         dp = [0] * (target + 1)
  5.         dp[0] = 1 # 凑够目标i一共有dp[i]中方法
  6.         for i in range(1, target + 1):
  7.             for num in nums:
  8.                 if i >= num:
  9.                     dp[i] += dp[i - num]
  10.          return dp[target]

https://leetcode-cn.com/problems/target-sum/solution/xi-wang-yong-yi-chong-gui-lu-gao-ding-bei-bao-we-2/

  • todo

https://leetcode-cn.com/problems/target-sum/solution/python-dfs-xiang-jie-by-jimmy00745/

  1. class Solution:
  2.     def findTargetSumWays(self, nums: List[int], S: int) -> int:
  3.         if sum(nums) < S or (sum(nums) + S) % 2 == 1: return 0
  4.         P = (sum(nums) + S) // 2
  5.         dp = [1] + [0 for _ in range(P)]
  6.         for num in nums:
  7.             for j in range(P,num-1,-1):
  8.                 dp[j] += dp[j - num]
  9.         return dp[P]