题解 | #目标和#

递归,路径选择

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @param target int整型 
# @return int整型
#
class Solution:
    def __init__(self):
        self.count = 0
    
    def findTargetSumWays(self , nums: List[int], target: int) -> int:
        # write code here
        self.targetSum(nums, [], target, 0)
        return self.count
    
    
    def targetSum(self, nums: List[int], path: List[int], target: int, start: int) -> None:
        if start > len(nums):
            return False
        if start == len(nums) and sum(path) == target:
            return True
        if start < len(nums) and self.targetSum(nums, path + [nums[start] * 1], target, start + 1):
            self.count = self.count + 1
        if start < len(nums) and self.targetSum(nums, path + [nums[start] * -1], target, start + 1):
            self.count = self.count + 1
        return False