The change at the register

Problem

Lupita works the register at the ice cream shop and half her shift goes into counting change. Of every coin in the register she has as many as she wants, and she wants to hand over the change with the fewest coins possible: fewer coins is less time counting.

Write a function that takes coins, a list of distinct positive whole numbers with the values in the register (they come in any order and the list may be empty), and amount, a whole number from 1 up: what has to be given back. Return the list of the coins of the change, from smallest to largest, with one entry for each coin she hands over. If those coins do not add up to the exact amount, return an empty list.

With coins of 1, 5, 10 and 25 and an amount of 40, the change is three coins: 5, 10 and 25.

Starting with the biggest coin does not always work out. With coins of 1, 5, 10, 21 and 25 and an amount of 63, three coins of 21 hit it exactly, while two of 25 leave 13 pending and force six coins.

If two different ways use the same number of coins, return the one that starts with the smallest coin; if they also tie there, the one that goes on with the smallest, and so on with the ones after that. With coins of 1, 5, 6 and 10 and an amount of 11 there are two ways of two coins, one of 5 with 6 and another of 1 with 10, and the one returned is 1 with 10. The amount never goes above 1000.

Examples

• The example

  [1, 5, 10, 25], 40 → [5, 10, 25]

• The biggest coin first does not work

  [1, 5, 10, 21, 25], 63 → [21, 21, 21]

• The biggest one gets in the way again

  [1, 10, 11], 20 → [10, 10]

• That change cannot be given

  [5, 10], 3 → []

• The coins come out of order

  [25, 1, 10, 5], 16 → [1, 5, 10]

Besides these, the challenge has hidden tests that are revealed when you submit your solution.

You start with this

def fewest_coins(coins, amount):
    pass

function fewestCoins(coins, amount) {
}