# Fast python branch and bound solution, beaten 99% python submissions

• ``````def coinChange(self, coins, amount):
if len(coins) == 0:
return -1
if amount == 0:
return 0

# try biggest coins first
sortedCoins = sorted(coins, reverse=True)

# upper bound on number of coins (+1 to represent the impossible case)
upperBound = (amount + sortedCoins[-1] - 1) / sortedCoins[-1] + 1

self.bestNCoins = upperBound

self.branchAndBoundSearch(sortedCoins, amount, 0)

if self.bestNCoins == upperBound:
return -1
else:
return self.bestNCoins

def branchAndBoundSearch(self, sortedCoins, amount, nCoins):
# lower bound on number of coins, achieved using the biggest coin
lowerBound = nCoins + (amount + sortedCoins[0] - 1) / sortedCoins[0]

if lowerBound > self.bestNCoins:
return

if len(sortedCoins) == 0:
return

# if amount matches the biggest coin, that is the solution
if amount == sortedCoins[0] and nCoins + 1 < self.bestNCoins:
self.bestNCoins = nCoins + 1
return

# try use the biggest coin
if amount > sortedCoins[0]:
self.branchAndBoundSearch(sortedCoins, amount - sortedCoins[0], nCoins + 1)

# else try not to use the biggest coin
if len(sortedCoins) > 1:
self.branchAndBoundSearch(sortedCoins[1:], amount, nCoins)``````

• Great fast solution! I'm a little surprised about `sortedCoins[1:]`, though. Have you also tried it with an index parameter instead? Is that slower/faster?

• Didn't try to optimize this code too much, you are right that it may be even faster with your suggestion.

• @alexli very smart. better than any dp solution

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