Get the change for a given value and available coins

cashier.js

/**
 * @link https://twitter.com/coproduto/status/1783128938149023804
 * @param {Number} value The value to be converted into coins
 * @param {Array<number>} coins The available coins
 * @returns {Array<number>} The coins that make up the value
 */
export function getChangeOptions(value, coins) {
  const sortedCoins = coins.slice().sort((a, b) => b - a)
  const changeOptions = []

  /**
   * 
   * @param {Number} remainingValue 
   * @param {Array<number>} currentCombination 
   * @param {Number} startIndex 
   * @returns {void}
   */
  const findCombinations = (remainingValue, currentCombination, startIndex) => {
    if (remainingValue === 0) {
      changeOptions.push(currentCombination.slice())
      return
    }

    for (let i = startIndex; i < sortedCoins.length; i++) {
      const coin = sortedCoins[i]
      if (coin <= remainingValue) {
        currentCombination.push(coin)
        findCombinations(remainingValue - coin, currentCombination, i)
        currentCombination.pop()
      }
    }
  }

  findCombinations(value, [], 0)

  return changeOptions
}

/**
 * 
 * @param {Array<Array<number>>} changeOptions
 * @returns {Array<number>}
 */
export const pickBestChangeOption = (changeOptions) => changeOptions.reduce((optimal, current) =>
  current.length < optimal.length ? current : optimal
)

cashier.test.js

import assert from 'node:assert'
import { describe, it } from 'node:test'

import { getChangeOptions } from './cashier.js'

describe('getChangeOptions', () => {
  it('should return the correct change options', () => {
    assert.deepStrictEqual(getChangeOptions(25, [25, 10, 5]), [
      [25],
      [10, 10, 5],
      [10, 5, 5, 5],
      [5, 5, 5, 5, 5]
    ])

    assert.deepStrictEqual(getChangeOptions(40, [25, 20, 10, 5]), [
      [25, 10, 5],
      [25, 5, 5, 5],
      [20, 20],
      [20, 10, 10],
      [20, 10, 5, 5],
      [20, 5, 5, 5, 5],
      [10, 10, 10, 10],
      [10, 10, 10, 5, 5],
      [10, 10, 5, 5, 5, 5],
      [10, 5, 5, 5, 5, 5, 5],
      [5, 5, 5, 5, 5, 5, 5, 5]
    ])
  })

  it('should pick the best change option', () => {
    assert.deepStrictEqual(pickBestChangeOption(getChangeOptions(25, [5, 10, 25])), [25])
    assert.deepStrictEqual(pickBestChangeOption(getChangeOptions(40, [5, 10, 20, 25])), [20, 20])
  })
})