```I made a slight modification to Paolo's solution, so it avoids
searching coin combinations that are permutations of others (i.e.,
[25, 1] and [1, 25]).  It does this by only allowing the system to add
coins at or beyond the last coin used in the combination being built.
So, if the coins are [25, 10, 5, 1], and we're building from 25, 10,
10, 5 then the next coin be only a 5 or a 1.  It seems to speed
Paolo's solution by about 30% on my system.

Eric

----

Are you interested in on-site Ruby training that's been highly
reviewed by former students?  http://LearnRuby.com

====

def make_change(a, list = [25, 10, 5, 1])
# to pass testcases :-P
return nil if a < 0
return nil if a != a.floor
parents = Array.new(a + 1)
parents = 0
worklist = [[0, 0]]
while parents[a].nil? && !worklist.empty? do
base, starting_index = worklist.shift
starting_index.upto(list.size - 1) do |index|
coin = list[index]
tot = base + coin
if tot <= a && parents[tot].nil?
parents[tot] = base
worklist << [tot, index]
end
end
end
return nil if parents[a].nil?
result = []
while a > 0 do
parent = parents[a]
result << a - parent
a = parent
end
result.sort!.reverse!
end

```