プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問をやる。今回は、Q05:いまだに現金払い？。しかし、無駄に煽りを効かせたタイトルだなぁ

Q: 1000札を両替したときにでてくる硬貨の組み合わせは何通りあるか？ただし、取り扱う硬貨は500円、100円、50円、10円のみとし、硬貨の枚数は最大で15枚とする。

def count(price:Int, coins:Seq[Int], max:Int):Int = {
  coins.sortWith((a,b) => a > b) match {
    case coin::Nil =>
      if(price/coin <= max) 1 else 0
    case coin::t =>
      (0 to price/coin).fold(0){
        (sum:Int, num:Int) => count(price - num*coin, t, max - num) + sum
      }
  }
}
count(1000, Seq(500, 100, 50, 10), 15)