LeetCode Entry

518. Coin Change II

11.08.2023 medium 2023 kotlin

Ways to make amount with array of coins

518. Coin Change II medium blog post substack image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/305

Problem TLDR

Ways to make amount with array of coins

Intuition

This is a classical Dynamic Programming problem: the result is only depending on inputs – coins subarray and the amount, so can be cached.

In a Depth-First search manner, consider possibilities of taking a coin and skipping to the next.

Approach

  • HashMap gives TLE, but an Array cache will pass

Complexity

  • Time complexity: \(O(nm)\)

  • Space complexity: \(O(nm)\)

Code


    fun change(amount: Int, coins: IntArray): Int {
      val cache = Array(coins.size) { IntArray(amount + 1) { -1 } }
      fun dfs(curr: Int, left: Int): Int = if (left == 0) 1
        else if (left < 0 || curr == coins.size) 0
        else cache[curr][left].takeIf { it >= 0 } ?: {
          dfs(curr, left - coins[curr]) + dfs(curr + 1, left)
        }().also { cache[curr][left] = it }
      return dfs(0, amount)
    }