数字の書いてあるN枚のカードから、足してAになる組み合わせの数をかぞえる

Main.scala

object Main {
  def main(args:Array[String]) = {
    val sc = new java.util.Scanner(System.in)
    val n, a = sc.nextInt
    val x = List.fill(n)(sc.nextInt)

    val nx = (a :: x).max * n

    val dpMemo = collection.mutable.ArrayBuffer.fill(n + 1, n + 1, nx + 1)(-1L)
    def dp(j: Int, k: Int, s: Int): Long = {
    	if (dpMemo(j)(k)(s) >= 0) return dpMemo(j)(k)(s)

    	val xj = x(j - 1)
    	val ret = if (j == 0 && k == 0 && s == 0) 1L
    		else if (j > 0 && s < xj) dp(j - 1, k, s)
    		else if (j > 0 && k > 0 && s >= xj) dp(j - 1, k, s) + dp(j - 1, k - 1, s - xj)
    		else 0L
    	dpMemo(j)(k)(s) = ret
    	ret
    }

    val ans = (1 to n).map(k => dp(n, k, k * a)).sum

    println(ans)

  }
}

http://abc044.contest.atcoder.jp/tasks/arc060_a
こちらのAtCoderの過去問です