#518

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Coin Change II

Calculate the number of unique coin combinations to reach a target amount using state transition dynamic programming efficiently.

array dynamic programming

Problem Statement

You are given an array of distinct integers representing coin denominations and a target amount. Each coin can be used unlimited times to form sums.

Return the total number of unique combinations that add up to the target amount. If no combination can form the amount, return 0.

Examples

Example 1

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

Output: 4

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

the amount of 3 cannot be made up just with coins of 2.

Example 3

Input: amount = 10, coins = [10]

Output: 1

Example details omitted.

Constraints

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

Solution Approach

Dynamic Programming Array Setup

Create an array dp of size amount+1 with dp[0]=1, representing one way to make amount 0. All other indices start at 0. This array tracks the number of ways to make each sub-amount.

State Transition Iteration

Iterate through each coin, and for each amount from coin to target, update dp[amount] += dp[amount - coin]. This ensures each combination counts once, reflecting the state transition dynamic programming pattern.

Return Result

After processing all coins, dp[amount] contains the total number of unique combinations. If dp[amount] remains 0, no valid combination exists for the target amount.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(amount * number of coins) since each coin updates all relevant dp indices. Space complexity is O(amount) using a single array for dynamic programming, capturing all state transitions efficiently.

What Interviewers Usually Probe

Expect candidates to recognize the need for a state-based dynamic programming solution.
Watch for proper handling of unlimited coin usage without double-counting combinations.
Check if candidate can optimize space using a single dp array instead of 2D approaches.

Common Pitfalls or Variants

Common pitfalls

Mistakenly counting permutations instead of combinations by updating the array incorrectly.
Initializing dp array incorrectly or forgetting dp[0] = 1, causing all results to be zero.
Iterating over amounts before coins, which can count duplicate combinations.

Follow-up variants

Change the target amount to a large value to test space-optimized dynamic programming.
Restrict coin usage to a maximum count per denomination to modify the state transition.
Compute minimum number of coins required instead of counting combinations for a variation.

FAQ

What is the main pattern used in Coin Change II?

The primary pattern is state transition dynamic programming, updating an array to track the number of ways to form each amount.

Can I use each coin only once in Coin Change II?

No, this problem assumes an infinite supply of each coin denomination, allowing repeated usage.

What happens if the amount is zero?

There is exactly one way to form amount zero: use no coins, so dp[0] = 1.

How do I avoid counting duplicate combinations?

Iterate over coins first and amounts second, updating dp[amount] += dp[amount - coin] to maintain unique combination counts.

What is the time complexity for Coin Change II?

Time complexity is O(amount * number of coins), as each coin iterates through all amounts up to the target.

terminal

Solution

Solution 1: Dynamic Programming (Complete Knapsack)

We define $f[i][j]$ as the number of coin combinations to make up the amount $j$ using the first $i$ types of coins. Initially, $f[0][0] = 1$, and the values of other positions are all $0$.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        m, n = len(coins), amount
        f = [[0] * (n + 1) for _ in range(m + 1)]
        f[0][0] = 1
        for i, x in enumerate(coins, 1):
            for j in range(n + 1):
                f[i][j] = f[i - 1][j]
                if j >= x:
                    f[i][j] += f[i][j - x]
        return f[m][n]

Continue Practicing

#526 beautiful arrangement #494 target sum #542 01 matrix