Fewest Number of Coins

More Details

To make $0.67 with American coins, 67 pennies work. But the fewest number of coins needed to make this change is 2 pennies, 1 nickel, 1 dime, 0 quarters and 1 fifty-cent piece. The answer would be {2, 1, 1, 0, 1}.

What Your Function Should Do

Write a function Coins that takes a list called values of positive integers and a positive integer target. Your function should return all lists of the number of coins to make the target with the fewest number of coins possible, all of whose denominations are in values. Return the list of ways in Sort order.

In the following example, the fewest number of coins to make 35 is 4. There is only one such case:

Coins[{1,2,4,8,16},35]

Verify these sum to 35:

1 1+1 2+0 4+0 8+2 16

Alternatively, verify with a dot product:

Coins[{1,2,4,8,16},35].{1,2,4,8,16}

More Examples

Coins[{1,5,10,25,50},67]

Coins[{1,2,3,8,5},9]

There may be multiple ways to use the fewest number of coins possible:

Coins[{2,3,8,5,11},9]

Coins[{11,13,17,19,23},100]

The list is returned in Sort order:

Coins[{11,13,17,19,23},100]===Sort[Coins[{11,13,17,19,23},100]]

If no such solution exists, the empty list {} is returned:

Coins[{2,4,6,8,10},17]

Coins[{x__Integer?Positive},target_Integer?Positive]:=