Python recursion with memoization, O(len(nums)*sum(nums))


  • 0
    I
    class Solution(object):
        def calc_ways_target(self, nums, S, idx, num_ways_cache):
            if idx == len(nums):
                return 1 if S == 0 else 0
                
            if (idx, S) in num_ways_cache:
                return num_ways_cache[(idx, S)]
            
            ways_with_plus = self.calc_ways_target(nums, S - nums[idx], idx+1, num_ways_cache)
            ways_with_minus = self.calc_ways_target(nums, S + nums[idx], idx+1, num_ways_cache)
            num_ways_cache[(idx, S)] = ways_with_plus + ways_with_minus
            return num_ways_cache[(idx, S)]
        
        def findTargetSumWays(self, nums, S):
            """
            :type nums: List[int]
            :type S: int
            :rtype: int
            """
            num_ways_cache = {}
            return self.calc_ways_target(nums, S, 0, num_ways_cache)

Log in to reply
 

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