Practice/Pinterest/Leetcode 518. Coin Change II

Leetcode 518. Coin Change II

CodingMust

Problem

You are given an array of distinct positive integers representing different coin denominations and a target amount. Determine how many different combinations of these coins can sum to the target amount. You have an unlimited supply of each coin denomination.

Note that combinations are distinct only if the selection of coins differs, not the order. For example, [1, 2] and [2, 1] are considered the same combination.

Requirements

1. Count the number of distinct combinations that sum to the target amount
2. Each coin denomination can be used multiple times
3. Return 0 if it's impossible to form the target amount
4. The order of coins in a combination does not matter

Constraints

• 0 ≤ amount ≤ 5000
• 1 ≤ coins.length ≤ 300
• 1 ≤ coins[i] ≤ 5000
• All values in the coins array are distinct
• Expected time complexity: O(n × m) where n is the amount and m is the number of coins
• Expected space complexity: O(n) or O(n × m)

Examples

Example 1:

` Input: amount = 5, coins = [1, 2, 5] Output: 4 Explanation: There are four ways to make the amount 5:

• 5 (use one coin of value 5)
• 2 + 2 + 1 (use two coins of value 2 and one coin of value 1)
• 2 + 1 + 1 + 1 (use one coin of value 2 and three coins of value 1)
• 1 + 1 + 1 + 1 + 1 (use five coins of value 1) `

Example 2:

Input: amount = 0, coins = [7] Output: 1 Explanation: There is exactly one way to make amount 0: use no coins at all.

Example 3:

Input: amount = 3, coins = [2] Output: 0 Explanation: The amount 3 cannot be formed using only coins of value 2.