Problem Statement

Given an integer array coins, where coins[i] = x represents the coin of amount x, and integer amount, return the total number of distinct ways to make a amount of money using a given set of coin denominations. If that amount of money cannot be made up by any combination of the coins, return 0.

You can have an infinite number of each coin.

Examples

• Example 1:

  • Input: amount = 4, coins = [1,2,3]
  • Expected Output: 4
  • Justification: The four ways to make 4 are: [1,1,1,1], [1,1,2], [2,2], and [1,3].

• Example 2:

  • Input: amount = 10, coins = [2, 5, 3, 6]
  • Expected Output: 5
  • Justification: The five ways to make 10 are: [2,2,2,2,2],[2,2,3,3], [5,5], [2,2,6], and [2,3,5]`.

• Example 3:

  • Input: amount = 0, coins = [7,3]
  • Expected Output: 1
  • Justification: There is only one way to make 0, which is by not using any coins at all.

Try it yourself

Try solving this question here: