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.

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.

Example 1:Input: coins = [1,2,5], amount = 11Output: 3Explanation: 11 = 5 + 5 + 1Example 2:Input: coins = [2], amount = 3Output: -1Example 3:Input: coins = [1], amount = 0Output: 0Constraints:1 <= coins.length <= 121 <= coins[i] <= 231 - 10 <= amount <= 104

Coin change problem

Now that we have understood the Coin Change problem, let’s check our knowledge by solving the question below:

You have coin denominations of 1, 3, and 4. What is the minimum number of coins needed to make a total amount of 6?

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.

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

def CC(coins, amount, change=[]):total = 0for 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 -1print('Number of coins required:', coinChange(coins=[2,15,1400], amount=2400))

Coin Change problem in Python

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.

The `CC`

function iterates through each coin denomination in the `coins`

list, potentially visiting each coin once. This results in a time complexity of `coins`

list adds an additional time complexity of

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

Copyright ©2024 Educative, Inc. All rights reserved

TRENDING TOPICS