My first solution is using dynamic programming. Then I want to also try breath-first-search. The first version of my BFS:

class Solution: def coinChange(self, coins: List[int], amount: int) -> int: if amount == 0: return 0 # bfs depth, ans = 1, -1 queue = [amount] while len(queue) > 0: new_queue = [] for node in queue: for coin in coins: if coin > node: continue if coin == node: return depth else: new_queue.append(node-coin) queue = new_queue depth += 1 return ans

It could get the correct answer but met TLE (Time Limit Exceeded) error when running the below case:

[2,3,5,7,11,13,17,19,21] 9999

After checking the variables “queue” and “new_queue”, I noticed there are many duplicate values. Therefore I set them to “set” instead of “list”:

class Solution: def coinChange(self, coins: List[int], amount: int) -> int: if amount == 0: return 0 # bfs depth, ans = 1, -1 queue = {amount} while len(queue) > 0: new_queue = set() for node in queue: for coin in coins: if coin > node: continue if coin == node: return depth else: new_queue.add(node-coin) queue = new_queue depth += 1 return ans

It’s faster but still costs about 5 seconds (This is too long for a contest in LeetCode).

Actually, there are still many duplicated values. Not in one “queue”, but in different depths. Let me take this case:

`Input: coins = [1,2,5], amount = 11`

as an example. The BFS of it looks like this:

The program already starts to check “9” at the second layer, so it’s just a waste of time to check “9” again in the third layer. Thus, we can ignore any number in “new_queue” that is already in all the previous “queues”.

I will add a new set called “already” to record all the values the program ALREADY TO PROCESS, and minus it before searching the next depth. The new code only costs 90ms:

class Solution: def coinChange(self, coins: List[int], amount: int) -> int: if amount == 0: return 0 # bfs depth, ans = 1, -1 queue = {amount} already = set() while len(queue) > 0: new_queue = set() for node in queue: for coin in coins: if coin > node: continue if coin == node: return depth else: new_queue.add(node-coin) already |= queue queue = new_queue - already depth += 1 return ans

———- 2023.01.24 ———-

Seems other BFS problems could also borrow this idea. Like this one I made https://leetcode.com/submissions/detail/884138668/