1. # 给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选
    2. # 择一个符号添加在前面。
    3. #
    4. #  返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
    5. #
    6. #
    7. #
    8. #  示例：
    9. #
    10. #  输入：nums: [1, 1, 1, 1, 1], S: 3
    11. # 输出：5
    12. # 解释：
    13. #
    14. # -1+1+1+1+1 = 3
    15. # +1-1+1+1+1 = 3
    16. # +1+1-1+1+1 = 3
    17. # +1+1+1-1+1 = 3
    18. # +1+1+1+1-1 = 3
    19. #
    20. # 一共有5种方法让最终目标和为3。
    21. #
    22. #
    23. #
    24. #
    25. #  提示：
    26. #
    27. #
    28. #  数组非空，且长度不会超过 20 。
    29. #  初始的数组的和不会超过 1000 。
    30. #  保证返回的最终结果能被 32 位整数存下。
    31. #
    32. #  Related Topics 深度优先搜索 动态规划
    33. #  👍 496 👎 0
    36. # leetcode submit region begin(Prohibit modification and deletion)
    37. class Solution(object):
    39.     def findTargetSumWays(self, nums, S):
    40.         """
    41.         :type nums: List[int]
    42.         :type S: int
    43.         :rtype: int
    44.         """
    45.         cache = {}
    47.         def get_res(index, sum):
    48.             if index == len(nums):
    49.                 if sum == 0:
    50.                     return 1
    51.                 return 0
    52.             if (index, sum) in cache:
    53.                 return cache[(index, sum)]
    54.             res = get_res(index + 1, sum + nums[index]) + get_res(index + 1, sum - nums[index])
    55.             cache[(index, sum)] = res
    56.             return res
    58.         return get_res(0, S)
    61. # leetcode submit region end(Prohibit modification and deletion)
    62. print(Solution().findTargetSumWays([40, 2, 49, 50, 46, 6, 5, 23, 38, 45, 45, 17, 4, 26, 40, 33, 14, 9, 37, 24], 7))