coins.js

// Coins

const COINS = [25, 10, 5, 1]
const TOTAL = 18

let storedValues = new Map()

function minCoins(coins, total) {
  let coinsUsed = getCoinsUsedInTotal(coins, total)

  console.log(`Total Number of Coins: ${coinsUsed.length}`)
  console.log(`Coins used: ${coinsUsed}`)
}


function getCoinsUsedInTotal(coins, total) {
  if (!total) {
    return []
  }

  if (storedValues.has(total)) {
    return storedValues.get(total)
  }

  let usedCoins = []

  for (let coin of coins) {
    if (coin > total) {
      continue
    }

    let remainder = total - coin
    let currentCoins = getCoinsUsedInTotal(coins, remainder)
    let isRemainderZero = (remainder === 0)
    let isCurrentCoinsFewerThanUsedCoins = (currentCoins.length < usedCoins.length)

    if (remainder >= 0) {
      if (isCurrentCoinsFewerThanUsedCoins || !usedCoins.length) {
        if (currentCoins.length || isRemainderZero) {
          usedCoins = [coin].concat(currentCoins)
        }
      }
    }
  }

  storedValues.set(total, usedCoins)

  return storedValues.get(total)
}

minCoins(COINS, TOTAL)