Time Limited Exceed Recursive Exhaustive Search - Python


  • 0
    V

    Hi guys, I am using this exhaustive search algorithm for this problem (not sure if this is categorized as any specific type of algorithm). Though exceeding time limit, it does work for several cases. I was trying to calculate the time complexity of this algorithm but couldn't come up with one with confidence. Could someone give a hand?

    Also, if there is a way to tweak this algorithm to pass the OJ, please let me know!

    Thanks.

    class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        
        if amount == 0:
            return 0
        
        self.result = float('Inf')
        tmpCount = 0
        self.helper(coins, amount, tmpCount)
        
        if self.result == float('Inf'): 
            return -1
        return self.result 
    
    def helper(self, coins, target, tmp):
        if target == 0:
            self.result = min(self.result, tmp)
            return
        
        for i in range(len(coins)):
            if coins[i] <= target:
                self.helper(coins[i:], target - coins[i], tmp + 1)

Log in to reply
 

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