Created
March 2, 2023 11:19
-
-
Save renanreismartins/8bf881818f6c36fab4aee6e988e852a6 to your computer and use it in GitHub Desktop.
needs memoization
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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(",")) | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment