Skip to main content
Back to ChallengesCoin Change IIHard 30 min

Coin Change II

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money. Return the number of combinations that make up that amount.

Examples

Input: amount = 5, coins = [1,2,5]
Output: 4
Combinations are: 5, 2+2+1, 2+1+1+1, 1+1+1+1+1

Constraints

  • • 1 <= coins.length <= 300
  • • 1 <= coins[i] <= 5000
  • • 0 <= amount <= 5000

Complexity Analysis

Time
O(coins.length * amount)
loops to accumulate possible sums.
Space
O(amount)
DP array storing paths count for each amount.

Test Cases

#1 Standard amount combinations
Input: 5, [1,2,5]
Expected: 4
#2 Impossible target amount
Input: 3, [2]
Expected: 0
#3 Single exact coin match
Input: 10, [10]
Expected: 1
Output
Click "Run Code" to see output here...