# Python with memoization gives TLE!

• The below, top down memoized implementation which is giving TLE. Any thoughts why?

EDIT: similar problem reported here - https://discuss.leetcode.com/topic/32489/java-both-iterative-and-recursive-solutions-with-explanations/6

``````from functools import wraps

def memo(func):
cache = {}
@wraps(func)
def wrap(*args):
if args not in cache:
cache[args] = func(*args)
return cache[args]
return wrap

class Solution(object):
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
if len(coins) == 0:
return -1

self.coins = coins
self.coins.sort(reverse=True)

return self.change(amount)

@memo
def change(self, amount):
if amount == 0:
return 0

if amount < 0:
return -1

minCoins = float('inf')

for coin in self.coins:
res = self.change(amount - coin)
if res > -1:
minCoins = min(minCoins, 1 + res)

return minCoins if minCoins != float('inf') else -1

``````

• @ohmygeek It has happened to me on multiple occasions. Just as I add a simple line to the start and the end of my recursive program. TLE pops up.

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