Solution of coin combination issue by paranoiase

coin.rb

# Solution of the coin combination issue.
# by paranoiase
#
# http://www.facebook.com/groups/rubykr
# https://github.com/rubykorea/codingdojo


require 'spec_helper'

class Coin
  def initialize(amount)
    @amount = amount
  end

  COINS = [50, 100, 500, 1000, 5000, 10000]
  def build_combinations(progress, container, cache = [])
    COINS.map do |coin|
      combination = progress.dup + [coin]
      combination.sort!

      next if cache.include? combination

      sum = combination.inject(&:+)
      if sum == @amount
        container << combination
      elsif sum < @amount
        cache << combination
        build_combinations(combination, container, cache)
      end
    end.compact
  end

  def count_combinations
    [].tap do |container|
      build_combinations([], container)
    end.uniq.count
  end
end

describe Coin do
  describe "#count_combinations" do
    it "should count all cases of coin combination" do
      coin = Coin.new(50)
      coin.count_combinations.should == 1

      coin = Coin.new(100)
      coin.count_combinations.should == 2

      coin = Coin.new(150)
      coin.count_combinations.should == 2

      coin = Coin.new(200)
      coin.count_combinations.should == 3

      coin = Coin.new(500)
      coin.count_combinations.should == 7

      coin = Coin.new(1700)
      coin.count_combinations.should == 53

      # coin = Coin.new(100_000)
      # coin.count_combinations.should == 49_330_996
    end
  end
end