Fast Python recursive solution


  • 0
    H

    Simple recursive solution with two optimizations:

    • buffer any intermediate results
    • terminate early if the sum out of the range of possible sums in the array
    class Solution(object):
        def findTargetSumWays(self, nums, S):
            """
            :type nums: List[int]
            :type S: int
            :rtype: int
            """
            n = len(nums)
            max_pos = sum(nums)
            dic = {}
            def rec(start, s,max_pos):
                if start == n:
                    return 1 if s ==0 else 0
                if s >max_pos or s<-max_pos:
                    return 0
                if (start,s) in dic:
                    return dic[(start,s)]
                res = rec(start+1, s- nums[start], max_pos - nums[start]) + rec(start+1, s+nums[start],max_pos - nums[start])
                dic[(start,s)] = res
                return res
                
            return rec(0,S,max_pos)
    

Log in to reply
 

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