needs memoization

BestSum.scala

object BestSum extends App {

  def bestSum(n: Int, coins: Array[Int]): Array[Int] = {

    if (n == 0) return Array[Int]()
    if (n < 0) return null

    var shortest: Array[Int] = null;

    for (coin <- coins) {
      val rest = n - coin
      val ints = bestSum(rest, coins)
      if (ints != null) {
        val combination = Array.concat(Array[Int](coin), ints)

        if (shortest == null || combination.length < shortest.length) {
          shortest = combination
        }
      }
    }

    shortest
  }


  println(bestSum(7, Array[Int](7)).mkString(","))
  println(bestSum(7, Array[Int](7)).mkString(","))
  println(bestSum(7, Array[Int](1)).mkString(","))
  println(bestSum(7, Array[Int](1, 7)).mkString(","))
  println(bestSum(7, Array[Int](7, 1)).mkString(","))
  println(bestSum(7, Array[Int]( 2, 3, 8, 7)).mkString(","))
  println()
  //println(howSum(300, Array[Int](7, 14)).mkString(","))
//  println(howSum(7, Array[Int](8)).mkString(","))
  println(bestSum(7, Array[Int](8, 7)).mkString(","))
  println(bestSum(7, Array[Int](5, 3, 4, 7)).mkString(","))
  println(bestSum(100, Array[Int](1, 2, 5, 25)).mkString(","))
}