Python DFS


  • 0
    class Solution(object):
        def findTargetSumWays(self, nums, S):
            self.h = {}
            return self.helper(nums,S, 0)
        
        def helper(self, nums, S, pos):
            s = str(pos) + '#' + str(S)
            if s in self.h:
                return self.h[s]
            if pos == len(nums):
                return 1 if S == 0 else 0
            if sum(nums[pos:]) < S:
                self.h[s] = 0
            else:
                self.h[s] = self.helper(nums, S+nums[pos], pos+1) + self.helper(nums, S-nums[pos], pos+1)
            return self.h[s]

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.