Coin Change II — Medium Coding Interview Question

Given an integer array coins representing coins of different denominations and an integer amount, return the number of combinations that make up that amount.

Example

Input: amount = 5, coins = [1,2,5]

Output: 4

Explanation: 5=5, 5=2+2+1, 5=2+1+1+1, 5=1+1+1+1+1

Constraints

• 1 ≤ coins.length ≤ 300
• 1 ≤ amount ≤ 5000

Topics & Companies

Topics: dp

Asked by: Amazon, Google, Meta, Microsoft

Optimal Solution Complexity

Time complexity: O(n × amount). Space complexity: O(amount).

Practice more

• All DSA Problems
• DSA Patterns