Find minimum coins to make change

Given a list of coins[] of different denominations with infinite supply of each of the coins. Find the minimum number of coins required to make the given sum. If it's not possible to make a change, return -1.

Hint

Starting with the target sum: The algorithm explores two possible paths for each coin:

• Include the coin: If the current coin is included, its value is subtracted from the remaining sum, and the process repeats recursively to find the optimal combination for the reduced sum using the same set of coin denominations.
• Exclude the coin: If the current coin is not included, the algorithm proceeds to evaluate the next coin in the list.

By iteratively exploring these two paths for every coin, the algorithm identifies the combination of coins that minimizes the total number required to reach the target sum.

• Python
• Javascript
•  Run

def count(coins, total):
  if (total < 0 or len(coins) <= 0):
    return float('inf')

  if total == 0:
    return 0

  return min(1 + count(coins, total - coins[0]), count(coins[1:], total))

coins = [25, 10, 5]
total = 30

coins.sort(reverse=True)

output = count(coins, total)

print(output if (output != float('inf')) else -1)

function count(coins, sum) {
  if (sum < 0 || coins.length <= 0) {
    return Infinity;
  }

  if (sum == 0) {
    return 0;
  }

  return Math.min(1 + count(coins, sum - coins[0]), count(coins.slice(1), sum));
}

const coins = [25, 10, 5];
const sum = 30;

coins.sort((a, b) => b - a);

const output = count(coins, sum);

console.log((output !=  Infinity) ? output : -1);