< Back




518. Coin Change II

Similar to knapsack problems, we're asked to choose coins from a coin list, and return the number of
unique ways we can combine the coins to reach a target amount.

It's easy to reason about this problem with a recursive, memoization solution because we have two
choices and two states:

  * Skip the current coin
  * Pick the current coin

Our two states are the current coin and the amount we currently have. If we reach the end of the
coins, we just recurse backwards. If we reach the amount, we found a unique combination. If we go
over the amount, we just backtrack again. At each stage of the recursion, we're looking to see what
happens if we skip or choose the current coin.

Looking at this iteratively, we're making the same choices, it's just a bit more difficult to convey
in code. We'll start off with a memoization table that records our solutions for how many unique
combinations we know of to create a target amount. The table ranges from 0 to amount + 1, and each
index represents the known number of ways to reach that target across all coin types. For table[0],
it's always initialized to 1 - there's only one unique way to create 0 value and that's to just pick
nothing.

We start with the last coin in the list, and we look backwards table[j - coins[i]], where j is the
current value we're trying to create. We're reusing previously solved problems to update the current
number of unique combinations to create j with coins[i]. Our base case of table[0] helps us carry
forward 1 coin in the event we have a method to create j with coins[i].

The recursive solution is as follows:


  class Solution:
      def change(self, amount: int, coins: List[int]) -> int:
          n = len(coins)

          @cache
          def dp(i: int, t: int) -> int:
              if i == n:
                  return 0

              if t == amount:
                  return 1

              if t > amount:
                  return 0

              return dp(i, coins[i] + t) + dp(i + 1, t)

          return dp(0, 0)


_ Time Complexity:

  O(n * t) - Where n is the number of coins and t is the target amount, we essentially DFS through
  this many choices.

_ Space Complexity:

  O(n * t) - Our recusrive stack will reach this size.


The iterative solution is as follows:


  class Solution:
      def change(self, amount: int, coins: List[int]) -> int:
          n = len(coins)
          T = [0 for _ in range(amount + 1)]
          T[0] = 1

          for i in range(n - 1, -1, -1):
              for j in range(coins[i], amount + 1):
                  T[j] += T[j - coins[i]]

          return T[-1]


_ Time Complexity:

  O(n * t) - We loop through t amounts, and we conduct the loop n times.

_ Space Complexity:

  O(t) - We maintain a memoization table size t + 1.