1029: 表达式的个数 [命题人 : 外部导入] 时间限制 : 1.000 sec 内存限制 : 128 m

Scala语言 小明买了15快的泡面，请问现在超市给小明找钱有多少种方法，打印出每种找钱的方法

object Main extends App {
  val noodles = 15 
  val bills = Array(1, 2, 5, 10, 20, 50, 100)
  val change = 100 - noodles 

  def calculateChange(bills: Array[Int], amount: Int): List[List[Int]] = {
    if (amount == 0) {
      // 
      List(List())
    } else if (amount < 0 || bills.isEmpty) {
      List()
    } else {
      val without = calculateChange(bills.tail, amount)
      val with = calculateChange(bills, amount - bills.head)
      without ::: with.map(bills.head :: _)
    }
  }
  val methods = calculateChange(bills, change)
  println(s"共有 ${methods.length} 种方法：")
  for (method <- methods) {
    println(method.mkString("[", ", ", "]"))
  }
}