The partition function at 100

P100.scala

object P100 extends App {
  private def p(bal: Int, summand: Int, m: Map[(Int, Int), Int]): (Int, Map[(Int, Int), Int]) =
    if (bal < 0 || summand == 100) (0, m)
    else if (bal == 0) (1, m)
    else {
      val (nSumsWithSummand, m1) = p0(bal - summand, summand, m)
      val (nSumsWithoutSummand, m2) = p0(bal, summand + 1, m1)
      (nSumsWithSummand + nSumsWithoutSummand, m2)
    }
  private def p0(b: Int, s: Int, m: Map[(Int, Int), Int]) =
    m.get((b, s)) match {
      case None => 
        val (nsws, m0) = p(b, s, m)
        (nsws, m0 + ((b, s) -> nsws))
      case Some(cachedNSums) => (cachedNSums, m)
    }
  println(p(100, 1, Map.empty)._1)
}