Python DP+Memoization is getting a TLE


  • 0
    G

    I am not sure why this is getting a TLE.

    class Solution(object):
        def helper(self, i, array, target, cache):
            if target == 0:
                return True
            elif target < 0 or i == len(array):
                return False
            else:
                if i in cache and target in cache[i]:
                    return cache[i][target]
                else:
                    cache.setdefault(i, {})
                    cache[i][target] = self.helper(i+1, array, target, cache)
                    if target-array[i] >= 0:
                        cache[i][target] = cache[i][target] or self.helper(i+1, array, target-array[i], cache)
                    return cache[i][target]
    
        def canPartition(self, nums):
            """
            :type nums: List[int]
            :rtype: bool
            """
            total = sum(nums)
            if total & 1:
                return False
            else:
                target = total // 2
            return self.helper(0, nums, target, {})
    

  • 0

    @tarun6 Done, this is fixed and your solution should get Accepted now.


Log in to reply
 

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