# Leetcode322: medium, BFS

catalogue

1. Title Description

2. Problem solving analysis

3. Code implementation

# 1. Title Description

Give you an integer array of coins to represent coins of different denominations; And an integer amount, representing the total amount.
Calculate and return the minimum number of coins required to make up the total amount. If no combination of coins can make up the total amount, return - 1. You can think that the number of coins of each kind is unlimited.

Example 1:
Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:
Input: coins = , amount = 3
Output: - 1

Example 3:
Input: coins = , amount = 0
Output: 0

Tips:
1 <= coins.length <= 12
1 <= coins[i] <= 2^31 - 1
0 <= amount <= 10^4

Source: LeetCode

# 2. Problem solving analysis

The minimum number of coins -- > the shortest path can be solved by breadth first search.

The amount (to be exchanged) is represented by the status of the node. The starting node value is total amount. Each (directed) edge represents the selected coin. After passing through the edge, the value of the adjacent node is equal to the value of the previous node minus the coin value represented by edge. Since the number of each coin is unlimited, all candidate coins can be considered when traversing its adjacent nodes from each "node". So... Search in a breadth first manner until you find the first node with a value of 0.

# 3. Code implementation

```import sys
import time
import random
from   collections import deque
from   typing import List

class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
assert(amount >= 0)
if amount == 0:
return 0
if amount < min(coins):
return -1

q = deque([amount])
visited = set()
layer = 1
while q:
# print('layer = {0}, q.len = {1}'.format(layer,len(q)))
n = len(q)
for _ in range(n): # Traverse the current layer
a = q.pop()
if a in coins:
return layer
# Add a's neighbours into q
for c in coins:
b = a - c
if b > 0 and b not in visited:
q.appendleft(b)
layer = layer + 1
return -1```
```if __name__ == '__main__':

import time
sln   = Solution()

# testcase1
coins = [1, 2, 5]
amount = 11
print(sln.coinChange(coins, amount))

# testcase2
coins = 
amount = 3
print(sln.coinChange(coins, amount))

# testcase3
coins = [1, 2, 5, 10, 20,50, 100]
amount = 1001
tStart= time.time()
print(sln.coinChange(coins, amount))
tElapsed = time.time() - tStart
print('tElapsed = ', tElapsed, ' (sec)')

# testcase3
coins = [470,35,120,81,121]
amount = 9825
tStart= time.time()
print(sln.coinChange(coins, amount))
tElapsed = time.time() - tStart
print('tElapsed = ', tElapsed, ' (sec)')```

Execution time: 424 ms, beating 99.17% of users in all # Python 3 # submissions

Memory consumption: 15.9 MB, beating 18.33% of users in all # Python 3 # submissions

Pass test case: 188 / 188

This problem can also be solved by dynamic programming.

Keywords: Python Algorithm leetcode bfs

Added by marco75 on Thu, 24 Feb 2022 03:59:29 +0200