'Kotlin Coin Change recursive functional approach

I'm trying to solve leetcode problem with next basic idea:

fun coinChange(coins: IntArray, amount: Int): Int {
    fun calc(source: Long, lvl: Int): Int =
        if (source == amount.toLong())
            lvl
        else if (source > amount)
            -1
        else
            coins
                .map { calc(source = source + it, lvl = lvl + 1) }
                .filter { it > 0 }
                .sorted()
                .firstOrNull() ?: -1


    return calc(source = 0, lvl = 0)
}

This algorithm looks correct, but it is very slow and fails the tests because of stack overflow. In that case I'm tried to speed up it a little bit, but now it's not working correctly:

fun coinChange(coins: IntArray, amount: Int): Int {
    val memoized = mutableMapOf<Int, Int>()

    fun calc(source: Int, lvl: Int): Int =
        if (source == amount)
            lvl
        else if (source > amount)
            -1
        else
            memoized.getOrElse(source) {
                val evaluated = coins
                    .reversed()
                    .map { calc(source = source + it, lvl = lvl + 1) }
                    .filter { it > 0 }
                    .minOrNull() ?: -1

                memoized[source] = evaluated
                evaluated
            }

    return calc(source = 0, lvl = 0)
}

For input coinChange(coins = intArrayOf(186, 419, 83, 408), amount = 6249) it's returns 36, but must be 20. Would you kindly help me?



Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source