LeetCode 518: Coin Change II Solution in Python – A Step-by-Step Guide

What Is LeetCode 518: Coin Change II?

In LeetCode 518: Coin Change II, you’re given an integer amount and an array coins of distinct coin denominations. Your task is to find the number of different combinations (order doesn’t matter) that sum to amount, with unlimited use of each coin type. For example, with amount = 5 and coins = [1, 2, 5], there are 4 ways: [1,1,1,1,1], [1,1,1,2], [1,2,2], [5]. This problem builds on LeetCode 322: Coin Change, shifting from minimum coins to counting combinations.

Problem Statement

• Input:
• amount (int): Target sum.
• coins (List[int]): Coin denominations.
• Output: Integer—number of ways to make amount.
• Rules: Unlimited coins; order doesn’t matter (combinations, not permutations).

Constraints

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

Examples

• Input: amount = 5, coins = [1,2,5]
• Output: 4
• Ways: [1,1,1,1,1], [1,1,1,2], [1,2,2], [5].
• Input: amount = 3, coins = [2]
• Output: 0
• Can’t make 3 with only 2¢ coins.
• Input: amount = 10, coins = [10]
• Output: 1
• Only way: [10].

Understanding the Problem: Counting Coin Combinations

To solve LeetCode 518: Coin Change II in Python, we need a method to count all unique combinations of coins that sum to amount, where order doesn’t matter (e.g., [1,2] is the same as [2,1]). A naive approach might generate all possible sequences, but with unlimited coins and amounts up to 5000, that’s inefficient. We’ll explore:

• Best Solution (1D DP Array): O(amount * n) time, O(amount) space—fast and space-efficient.
• Alternative Solution (2D DP Table): O(amount n) time, O(amount n) space—detailed but bulkier.

Let’s dive into the 1D DP solution with a friendly breakdown!

Best Solution: Dynamic Programming with 1D Array

Why 1D DP Wins

The 1D DP array is the best for LeetCode 518 because it efficiently counts combinations using minimal space—O(amount)—while running in O(amount * n) time (n = number of coins). It builds the solution incrementally, avoiding the overhead of a full 2D table. It’s like tallying coin options one denomination at a time, keeping only what we need!

How It Works

Think of this as a coin-counting piggy bank:

• Step 1: Define DP Array:
• dp[j]: Number of ways to make amount j using coins considered so far.
• Step 2: Initialize:
• dp[0] = 1 (one way to make 0: use no coins).
• Step 3: Iterate Coins:
• For each coin c, update dp[j] for j >= c:
• dp[j] += dp[j - c] (add ways using this coin).
• Step 4: Return:
• dp[amount]—total ways to make amount.
• Why It Works:
• Outer loop on coins ensures combinations (not permutations).
• Cumulative updates count all possibilities.

It’s like a coin combo calculator!

Step-by-Step Example

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

• Init: dp = [1, 0, 0, 0, 0, 0] (size 6 for 0 to 5).
• Coin 1:
• j=1: dp[1] += dp[0] = 0 + 1 = 1.
• j=2: dp[2] += dp[1] = 0 + 1 = 1.
• j=5: dp[5] += dp[4] = 0 + 1 = 1.
• dp = [1, 1, 1, 1, 1, 1] (ways with just 1s).
• Coin 2:
• j=2: dp[2] += dp[0] = 1 + 1 = 2.
• j=3: dp[3] += dp[1] = 1 + 1 = 2.
• j=4: dp[4] += dp[2] = 1 + 2 = 3.
• j=5: dp[5] += dp[3] = 1 + 2 = 3.
• dp = [1, 1, 2, 2, 3, 3].
• Coin 5:
• j=5: dp[5] += dp[0] = 3 + 1 = 4.
• dp = [1, 1, 2, 2, 3, 4].
• Result: dp[5] = 4.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        # Step 1: Initialize DP array
        dp = [0] * (amount + 1)
        dp[0] = 1  # Base case: 1 way to make 0

        # Step 2: Iterate over each coin
        for coin in coins:
            # Update dp for amounts >= coin
            for j in range(coin, amount + 1):
                dp[j] += dp[j - coin]

        # Step 3: Return ways to make amount
        return dp[amount]

• Line 4: Array for amounts 0 to amount.
• Line 5: dp[0] = 1—no coins used.
• Line 8: Loop over coins (combinations).
• Lines 9-10: For each amount j, add ways using current coin.
• Line 13: Result for full amount.
• Time Complexity: O(amount * n)—nested loops.
• Space Complexity: O(amount)—1D array.

It’s like a coin-counting wizard!

Alternative Solution: 2D DP Table

Why an Alternative Approach?

The 2D DP table approach tracks combinations using both coins and amounts, offering a more detailed view. It’s O(amount * n) time and O(amount * n) space—intuitive for DP beginners but less space-efficient. Great for understanding the full state space!

How It Works

Picture this as a coin-amount grid:

• Step 1: Define dp[i][j]: Ways to make amount j using first i coins.
• Step 2: Base case—dp[0][0] = 1 (no coins, amount 0).
• Step 3: Fill table:
• Don’t use coin i: dp[i][j] = dp[i-1][j].
• Use coin i: dp[i][j] += dp[i][j - coins[i-1]] (if j >= coins[i-1]).
• Step 4: Return dp[n][amount].

It’s like a coin combo matrix!

Step-by-Step Example

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

• Init: dp = [[0]*6 for _ in range(3)], dp[0][0] = 1.
• Coin 1 (i=1):
• j=0: dp[1][0] = dp[0][0] = 1.
• j=1: dp[1][1] = dp[0][1] + dp[1][0] = 0 + 1 = 1.
• j=5: dp[1][5] = dp[0][5] + dp[1][4] = 0 + 1 = 1.
• Coin 2 (i=2):
• j=2: dp[2][2] = dp[1][2] + dp[2][0] = 1 + 1 = 2.
• j=5: dp[2][5] = dp[1][5] + dp[2][3] = 1 + 1 = 2.
• Result: dp[2][5] = 2.

Code for 2D DP Approach

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        n = len(coins)
        dp = [[0] * (amount + 1) for _ in range(n + 1)]
        dp[0][0] = 1  # Base case

        for i in range(1, n + 1):
            for j in range(amount + 1):
                dp[i][j] = dp[i-1][j]  # Don’t use coin
                if j >= coins[i-1]:
                    dp[i][j] += dp[i][j - coins[i-1]]  # Use coin

        return dp[n][amount]

• Time Complexity: O(amount * n)—fill table.
• Space Complexity: O(amount * n)—2D array.

It’s a detailed coin counter!

Comparing the Two Solutions

• 1D DP (Best):
• Pros: O(amount * n), O(amount) space, efficient.
• Cons: Less explicit.
• 2D DP (Alternative):
• Pros: O(amount * n), clear state.
• Cons: O(amount * n) space.

1D DP wins for efficiency!

Additional Examples and Edge Cases

• ** 0, [1]: 1.
• ** 1, [2]: 0.
• ** 5, [1,2,5]: 4.

1D DP handles them all!

Complexity Recap

• 1D DP: Time O(amount * n), Space O(amount).
• 2D DP: Time O(amount n), Space O(amount n).

1D DP’s the lean champ!

Key Takeaways

• 1D DP: Space saver—learn at Python Basics!
• 2D DP: Full picture.
• Combinations: Order matters not.
• Python: Arrays shine!

Final Thoughts: Count Those Coins!

LeetCode 518: Coin Change II in Python is a delightful DP challenge. The 1D DP array is your fast track, while the 2D table adds depth. Want more? Try LeetCode 322: Coin Change or LeetCode 377: Combination Sum IV. Ready to count? Head to Solve LeetCode 518 on LeetCode and tally those combinations today!