Coin Change Solver

coin.rb

require 'rubygems'
require 'pry'

VALID_COINS = [1, 5, 10, 25, 50]

def change(amount)
  change_iter(amount, VALID_COINS).each do |item|
    puts item.inspect
  end
end

def change_iter(amount, coin_list)
  first_coin = coin_list.first
  amount_after_first = amount - first_coin

  if amount_after_first == 0
    return [[first_coin]]
  elsif amount_after_first < 0
    return []
  else
    ret = change_iter(amount_after_first, coin_list).map do |item|
      item.push(first_coin)
    end
    
    ret += change_iter(amount, coin_list[1..-1]) do |item|
      item.push(first_coin)
    end

    return ret
  end

end

change(45)