Incrementally improving my recursive solution to the problem: "How many combinations of 25c, 10c and 5c coins are there that add up to 75c?"

coins.rb

#!/usr/bin/env ruby

def coins1(left, collection = [])
  if left == 0
    [collection.sort]
  elsif left >= 25
    coins1(left - 25, collection + [25]) +
      coins1(left - 10, collection + [10]) +
      coins1(left - 5, collection + [5])
  elsif left >= 10
    coins1(left - 10, collection + [10]) +
      coins1(left - 5, collection + [5])
  elsif left >= 5
    coins1(left - 5, collection + [5])
  else
    return []
  end
end

def coins2(left, collection = [])
  if left < 0 # not a solution
    []
  elsif left == 0 # a solution
    [collection.sort]
  else # keep looking
    coins2(left - 25, collection + [25]) +
      coins2(left - 10, collection + [10]) +
      coins2(left - 5, collection + [5])
  end
end

def coins3(left, values, collection = [])
  if left < 0 # not a solution
    []
  elsif left == 0 # a solution
    [collection.sort]
  else # keep looking
    values.map{|v| coins3(left - v, values, collection + [v]) }.inject(&:+)
  end
end

require 'set'

def coins4(left, values, collection = [])
  if left < 0 # not a solution
    Set.new
  elsif left == 0 # a solution
    Set.new [collection.sort]
  else # keep looking
    values.map{|v| coins4(left - v, values, collection + [v]) }.inject(&:+)
  end
end

puts coins1(75).uniq.map(&:inspect)
puts coins2(75).uniq.map(&:inspect)
puts coins3(75, [25, 10, 5]).uniq.map(&:inspect)
puts coins4(75, [25, 10, 5]).map(&:inspect) # easier to call
puts
puts coins4(75, [25, 10, 5]).size

# Output:
#
# [25, 25, 25]
# [5, 10, 10, 25, 25]
# [5, 5, 5, 10, 25, 25]
# [5, 5, 5, 5, 5, 25, 25]
# [10, 10, 10, 10, 10, 25]
# [5, 5, 10, 10, 10, 10, 25]
# [5, 5, 5, 5, 10, 10, 10, 25]
# [5, 5, 5, 5, 5, 5, 10, 10, 25]
# [5, 5, 5, 5, 5, 5, 5, 5, 10, 25]
# [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 25]
# [5, 10, 10, 10, 10, 10, 10, 10]
# [5, 5, 5, 10, 10, 10, 10, 10, 10]
# [5, 5, 5, 5, 5, 10, 10, 10, 10, 10]
# [5, 5, 5, 5, 5, 5, 5, 10, 10, 10, 10]
# [5, 5, 5, 5, 5, 5, 5, 5, 5, 10, 10, 10]
# [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 10, 10]
# [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 10]
# [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5]
#
# 18
#