algoadvance

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. If that amount of money cannot be made up by any combination of the coins, return 0.

You may assume that you have an infinite number of each kind of coin.

Example 1:

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

Example 2:

• Input: amount = 3, coins = [2]
• Output: 0
• Explanation: The amount of 3 cannot be made up just with coins of 2.

Example 3:

• Input: amount = 10, coins = [10]
• Output: 1

Clarifying Questions

1. Can the array of coins be empty?
   • Yes. If coins is empty, then the solution should be 0 for any positive amount.
2. Can the amount be 0?
   • Yes. If amount is 0, the number of ways to make the amount is 1 (by choosing no coins).
3. Are negative amounts or coin denominations allowed?
   • No. Both amount and coin denominations are assumed to be non-negative integers.

With the problem statement clear, let’s proceed to the next steps.

Strategy

We can solve this problem using Dynamic Programming. The idea is to use a list dp where dp[i] represents the number of ways to get the amount i using the available coins.

1. Initialize a list dp of size amount + 1 with all values set to 0, except dp[0] which should be 1 (since there’s one way to make amount 0: using no coins).
2. For each coin in the list coins, update the dp list for all amounts that can include this coin from coin to amount.

The final answer will be in dp[amount].

Code

def change(amount: int, coins: List[int]) -> int:
    # Initialize dp array
    dp = [0] * (amount + 1)
    dp[0] = 1
    
    # Iterate over each coin
    for coin in coins:
        for x in range(coin, amount + 1):
            dp[x] += dp[x - coin]

    return dp[amount]

Time Complexity

• Time Complexity: O(N * M), where N is the amount and M is the number of coins. This is because we traverse the coins list, and for each coin, we update the dp array for amount times.

• Space Complexity: O(N), where N is the amount. This is due to the space used by the dp array.

This approach ensures we efficiently compute the number of ways to reach the given amount using the provided coins, employing dynamic programming to avoid redundant calculations.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?