题目

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

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

示例 1:**

输入: nums: [1, 1, 1, 1, 1], S: 3
输出: 5
解释: 
-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
一共有5种方法让最终目标和为3。

注意:

数组非空，且长度不会超过20。
初始的数组的和不会超过1000。

保证返回的最终结果能被32位整数存下。

方案一（DFS）

def findTargetSumWays(nums: [int], S: int) -> int:
  kind = 0
  length = len(nums) # 性能优化, 一个长度为20的 nums 数组中, 假如下述判断条件都是用 len(nums) 用 cProfile 得到 被调用 3145727 次, i7 7700HQ CPU 上总耗时约为 0.12秒
  def dfs(index, count):
      '''
      index: 当前索引
      count: 前面的和

      如何优化？让递归提前结束，排除掉肯定不满足的——参考方案二
      '''
      nonlocal kind
      if index < length:
          dfs(index + 1, count + nums[index])
          dfs(index + 1, count - nums[index])
      elif count == S:
          kind += 1

  dfs(0, 0)
  return kind

直接使用DFS进行搜素

leetcode 执行超时

方案二（DFS with memory）

def findTargetSumWays(nums: [int], S: int) -> int:
  # 当前节点有多少可能的解 = (当前节点 + 后面的元素)的解的个数 + (当前节点 - 后面的元素)的解的个数
  d = {}  # key: (index, count); value: int, 表示当前元祖递归到最后又多少可能的解

  def dfs(curr_index, count):
      if (curr_index, count) in d:
          return d[(curr_index, count)]
      elif curr_index < len(nums):
          d[(curr_index, count)] = dfs(curr_index + 1, count + nums[curr_index]) + dfs(curr_index + 1, count - nums[curr_index])
          return d[(curr_index, count)]
      elif count == S:
          return 1
      else:
          return 0

  return dfs(0, 0)

主要是要找到memory，以及递归条件。

优化后的代码

def findTargetSumWays(nums: [int], S: int) -> int:
    # 当前节点有多少可能的解 = (当前节点 + 后面的元素)的解的个数 + (当前节点 - 后面的元素)的解的个数
    d = {}  # key: (index, count); value: int, 表示当前元祖递归到最后又多少可能的解
    def dfs(index, count):
        if (index, count) not in d and index < len(nums):
            d[(index, count)] = dfs(index + 1, count + nums[index]) + dfs(index + 1, count - nums[index])
        return d.get((index, count), int(count == S))

    return dfs(0, 0)

原文

https://leetcode-cn.com/explore/learn/card/queue-stack/219/stack-and-dfs/885/