How to solve LeetCode’s Coin Change problem

The Coin Change problem in LeetCode is a classic algorithmic problem that deals with finding the minimum number of coins needed to make a specific amount of money (often referred to as the target amount) using a given set of coin denominations. There are two coin chain problems: the minimum coins problem and the coin change combination problem. In this answer, we’ll attempt to solve the first of them.

Problem statement

We have a coins array with different coin values and a total amount of money represented by the amount integer. The task is to find the smallest number of coins needed to make up the given amount. If it’s impossible to reach the exact amount using any combination of the available coins, return -1. We can assume that we have an unlimited supply of each type of coin.

Algorithm

Now that we’ve understood the problem, let’s understand it programmatically.

We can construct an $N$ -array tree, with $N$ branches at each node, where $N$ represents the number of unique coins.
We will traverse the tree in a depth-first-search operation using recursion; if we sort the coins array in decreasing order, this will enable us to find the combination with the fewest number of coins first.
As we traverse the tree, we will compute the total amount at the current step, and if the total is equal to the amount, we will return the number of coins in the change array.
If the total is less than the amount, we will recursively move further down the tree.

Coding example

Let’s see the solution to the Coin Change problem:

def CC(coins, amount, change=[]):
    total = 0
    for coin in coins:
        change.append(coin)
        total = sum(change)
        if total == amount:
            print("Here is the change", change)
            return len(change)
        elif amount > total:
            return CC(coins, amount, change)
        change.pop(-1)
def coinChange(coins, amount):
    coins = sorted(coins, reverse=True)
    change = CC(coins=coins, amount=amount)
    return change if change else -1
print('Number of coins required:', coinChange(coins=[2,15,1400], amount=2400))

Coin Change problem in Python

Code explanation

Here's the explanation of Python code:

Line 1: We define a function named CC that takes three parameters: coins, amount, and change. Here, coins is a list of coin denominations, amount is the target amount of change to make, and change is a list for tracking the current combination of coins being considered. The change parameter is optional and defaults to an empty list.
Line 2: We initialize the total variable to 0 to keep track of the current sum of coins in the change list.
Lines 3–11: We iterate through each coin denomination in the coins list, appending them one by one to the change list. We calculate the total sum of coin denominations in the change list and check if it equals the target amount. If the total matches the target, it signifies a combination of coins that make up the required change, which is then printed out. The function returns the number of coins in the combination. If the target amount is greater than the current total, the function recursively calls itself with updated parameters to continue searching for a valid combination. Backtracking is facilitated by removing the last coin denomination from the change list. This recursive approach allows for a thorough exploration of possible coin combinations until a satisfactory solution is found or all possibilities are exhausted.
Lines 13–16: We define a function named coinChange that takes two parameters: coins and amount. Here, coins is a list of coin denominations, and amount is the target amount of change to make. This function sorts the coins list in descending order to prioritize larger denominations. This optimization aims to minimize the total number of coins required for the change. We then call the CC function with the sorted coins list and target amount, and then we assign the result to the change variable. Finally, the function returns the change value if it exists, indicating a successful combination, or -1 otherwise, signifying an inability to fulfill the required change with the given coins.

Time complexity

The CC function iterates through each coin denomination in the coins list, potentially visiting each coin once. This results in a time complexity of $O(n)$ , where $n$ is the number of coin denominations. Since the function is recursive, in the worst-case scenario, it might recursively call itself multiple times until finding a solution or exhaustively searching through all possible combinations. It may also explore all possible combinations of coins, resulting in an exponential time complexity. Sorting the coins list adds an additional time complexity of $O(n \space \text{log} \space n)$ , where $n$ is the number of coin denominations.

Space complexity

The space complexity is primarily determined by the recursion stack and the size of the change list. Since the change list stores the current combination of coins being considered; its size can grow up to the total number of coin denominations. Therefore, the space complexity of the change list is $O(n)$ , where $n$ is the number of coin denominations. Additionally, the space complexity of the recursion stack is determined by the maximum depth of recursion, which depends on the number of recursive calls made. In the worst case, if the function exhaustively searches through all possible combinations, the recursion depth could be proportional to the number of coin denominations, resulting in a space complexity of $O(n)$ .

Free Resources

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments