Coin Change II Leetcode Problem 518 [Python Solution]

Coin Change II LeetCode Problem 518 [Python Solution]

Problem Overview

The Coin Change II problem is a classic dynamic programming problem that falls under the category of 2-D Dynamic Programming.

It is featured on LeetCode as problem number 518 and is categorized as a medium difficulty problem.

The problem statement is as follows:

Problem Statement:
You are given an integer array coins, representing coins of different denominations, and an integer amount, representing a total amount of money.

Your task is to return the number of combinations that make up that amount using the given coins.

If it's impossible to make up the amount with the provided coins, return 0. You can assume that you have an infinite number of each kind of coin, and the answer is guaranteed to fit into a signed 32-bit integer.

To better understand the problem, let's consider an example:

Example:

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


In this example, given an amount of 5 and coins of denominations 1, 2, and 5, there are four different combinations to make up the amount.

Your task is to find the number of such combinations.

Understanding the Constraints

Before we delve into the solution, let's break down the problem and understand the constraints.

• 1 <= coins.length <= 300: This constraint means that the number of coins provided can range from 1 to 300, indicating a potential variation in the number of available denominations.
• 1 <= coins[i] <= 5000: Each coin denomination is within the range of 1 to 5000, which means that the values of individual coins can vary widely.
• All the values of coins are unique: This ensures that there are no duplicate coin denominations in the input.
• 0 <= amount <= 5000: The target amount you need to make up can be between 0 and 5000, including the possibility of making up zero.

These constraints shape the problem and provide the boundaries within which our solution must operate.

Problem Solution

Bruteforce Approach

A straightforward approach to solving this problem is to use recursion, considering all possible combinations.

However, this approach can be highly inefficient and result in exponential time complexity.

def change(amount, coins, index=0):
    # Base cases
    if amount == 0:
        return 1
    if amount < 0 or index == len(coins):
        return 0
    
    # Two choices: Use the current coin or skip it
    use_coin = change(amount - coins[index], coins, index)
    skip_coin = change(amount, coins, index + 1)
    
    return use_coin + skip_coin

In this recursive approach, we start from the first coin and consider two choices at each step: either we use the current coin or skip it.

We continue this process for each coin denomination until we reach the target amount.

This approach provides the correct result but is highly inefficient and leads to a time complexity of O(2^n), where n is the number of coins.

Related Interview Questions By Company:

• Word Break LeetCode
• Swap Nodes In Pairs LeetCode
• Asteroid Collision LeetCode

Related Interview Questions By Difficulty:

• Longest Palindromic Subsequence LeetCode
• Best Time To Buy And Sell Stock With Cooldown LeetCode
• Regular Expression Matching LeetCode

An Efficient Approach with Dynamic Programming

To improve efficiency and reduce the time complexity, we can use dynamic programming.

Dynamic programming involves breaking the problem down into smaller subproblems and storing the results of these subproblems in a table (usually an array or matrix) to avoid redundant calculations.

In this case, we can use a two-dimensional table dp, where dp[i][j] represents the number of ways to make up the amount j using the first i coin denominations.

def change(amount, coins):
    # Create a 2D array to store results
    dp = [[0] * (amount + 1) for _ in range(len(coins) + 1)]

    # Initialize base case: There's one way to make amount 0 with no coins.

for i in range(len(coins) + 1):
        dp[i][0] = 1

    for i in range(1, len(coins) + 1):
        for j in range(1, amount + 1):
            if j >= coins[i - 1]:
                # Two choices: use the current coin or skip it
                use_coin = dp[i][j - coins[i - 1]]
                skip_coin = dp[i - 1][j]
                dp[i][j] = use_coin + skip_coin
            else:
                # If the current coin is too large to be used, skip it
                dp[i][j] = dp[i - 1][j]

    return dp[len(coins)][amount]

Here's how this dynamic programming solution works:

1. We initialize a 2D array dp

   where dp[i][j] represents the number of ways to make up the amount j using the first i coin denominations.

2. We initialize the base case: There's one way to make up amount 0 with no coins, so dp[i][0] is set to 1 for all i.

3. We iterate through the coins and the target amount, filling in the dp table by considering two choices at each step:

   • Using the current coin (use_coin): This is equivalent to reducing the target amount by the value of the current coin and looking up the number of ways to make up the remaining amount using the same set of coins.
   • Skipping the current coin (skip_coin): This is equivalent to looking up the number of ways to make up the target amount using the previous set of coins (i.e., without the current coin).

4. We update dp[i][j] based on these two choices, considering the condition that j must be greater than or equal to the current coin's value.

5. Finally, we return dp[len(coins)][amount], which represents the number of ways to make up the given amount using all the available coins.

This dynamic programming approach significantly improves the efficiency of solving the Coin Change II problem, with a time complexity of O(amount * len(coins)) and a space complexity of O(amount * len(coins)).

It efficiently handles the constraints of the problem and provides a fast and reliable solution.