As mentioned in this answer , some coin combinations may succumb to the greedy algorithm, but this does not guarantee that greed will give you the best mix for all coin combinations.
The following is a comprehensive, recursive solution in Python (ideal language for pseudo-code).
Note that this gives you permutations, not combinations, but if you want to filter out duplicates (in terms of combinations), it would just sort and filter after creating the list.
We also note that this can be quite terrible for large amounts. For example, while it is well below the second for input values such as 27 or 75, entering 1024 takes at least a couple of minutes before I get bored and cancel it).
import sys oldcount = 99999999 lst = [] def recurse (str, amt, count): global oldcount global lst if amt < 0: return if count > oldcount: return if amt == 0: if count < oldcount: print "=====" lst = [] oldcount = count if count == oldcount: lst.append (str) return recurse ("%s 19" % str, amt - 19, count + 1) recurse ("%s 13" % str, amt - 13, count + 1) recurse ("%s 7" % str, amt - 7, count + 1) recurse ("%s 1" % str, amt - 1, count + 1) recurse ("", int (sys.argv[1]), 0)
Note that for the names {1, 7, 13, 19} (in this particular case), the greedy algorithm is the best, the "proof" of this follows (a) :
For any values from 1 to 6, you need to use a lot of moments 1 , which gives you a greedy algorithm.
For any value from 7 to 12, you can use many coins 1 or 7 with seven less than 1 coins. The greedy algorithm gives you the last case, which is correct, because it is better to remove seven coins 1 and add one coin 7 - it reduces the number of coins by six.
For values 13 through 18, you cannot use 13 and a 7 , as this will be a minimum of 20 , so you are stuck in a mix of 13/1 or 7/1 (all coins 1 missing for the same reason as in the previous paragraph - replacement of 13 1 coins for one coin 13 is a massive decrease). Obviously, the best option for a value of 13 is a single coin 13 , but 14 can be reached with either 7/7 or 13/1 (both two coins). Then the values from 15 to 18 just added coins 1 .
Similarly, a value of 19 is the only coin 19 , while a value of 20 can be represented as 19/1 or 13/7 . Values 21 through 37 (immediately before 19/19 38) are 19 plus the minimum combination of the previous three paragraphs.
So, due to the selected values ( 1 and 7 are not comparable, 7/7 == 13/1 , 7/7/7 == 19/1/1 , 13/7 == 19/1 and so on), greedy the algorithm works just fine (I don’t think that these values were chosen randomly, this is too convenient).
Table of minimum coin values:
Value Count Possibilities 1 1 1 2 2 1x2 3 3 1x3 4 4 1x4 5 5 1x5 6 6 1x6 7 1 7 8 2 7,1 9 3 7,1x2 : 12 6 7,1x5 13 1 13 14 2 13,1 or 7x2 15 2 13,1x2 or 7x2,1 : 18 6 13,1X5 or 7x2,1x4 19 1 19 20 2 19,1 or 13,7 21 3 19,1x2 or 13,7,1 or 7x3 :
etc.
(a) Not formal evidence, but I’m sure that I’m right that I will redirect 20 questions / answers to the first person who shows me a counter example (providing questions and answers is not complete rubbish, of course - I should think that they are useful so as not to spoil the voting process).