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!
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)