ある金額になる硬貨の組み合わせを求めるメソッド

gistfile1.rb

#! ruby

# coins.sort.reverse!

def calc(sum, coins)
  if coins.size == 1
    return (sum % coins[0] == 0) ? 1 : 0
  end
  count = 0
  num = coins[0]
  0.upto(sum / num) do |i|
    count += calc(sum - (num * i), coins[1..-1])
  end
  count
end