Skip to content

LC 322. Coin Change (Medium)

mccornet edited this page Jul 26, 2021 · 9 revisions

Python

class Solution:

    def coinChange(self, coins: list[int], amount: int) -> int:
        from collections import deque
        # Store Change, Search depth. 
        # Search depth is the number of coins
        # Provide an initial case for zero change
        coin_change_depth = {0: 0}

        # Build up a BFS queue of coin combinations
        # Start with zero paid (adding a node to tree)
        coin_combinations = deque([0])

        while coin_combinations:
            coin_change = coin_combinations.popleft()

            # BFS: the match was reached via the shortest path
            if coin_change == amount: 
                return coin_change_depth[amount]

            for coin in coins:
                next_payment = coin_change + coin

                # Skip overshoot payments 
                # End case in recursion
                if next_payment > amount: continue

                # Skip payments already made 
                # via a previous BFS coin change route
                if next_payment in coin_change_depth: continue

                # Add the current change and depth to the dict
                # And add this to the queue of payment possibilities
                coin_change_depth[next_payment] = coin_change_depth[coin_change] + 1
                coin_combinations.append(next_payment)

        return -1  # No combination could reach the result        

Clone this wiki locally