518. Coin Change 2
Model: qwen3.5:9b
Topics:
FAANG asked: 1
Acceptance rate: 52.1%
Problem Breakdown
We are given an integer target amount and a list of coin denominations with infinite supply for each type. The goal is to calculate the total number of unique combinations that sum up exactly to the amount.
Key constraints:
- Order does not matter: This distinguishes it from permutations (e.g.,
[2, 3]and[3, 2]are considered one combination). We must count distinct sets of coins. - Infinite Supply: Each coin can be used multiple times.
- Edge Cases:
amount = 0: Technically there is one way (using no coins), though often test cases expect this to return 1 based on DP base case logic.- Empty
coinslist: If amount > 0, result should be 0. - Impossible amounts: Return 0 if the target cannot be formed by any subset of given denominations.
Intuition
A naive recursive approach would try every coin at every step to reach the sum. However, this naturally counts permutations (e.g., 1+2 and 2+1) rather than combinations unless we strictly enforce an order on which coins are considered first.
To optimize from exponential recursion: We recognize this as a variation of the Unbounded Knapsack Problem where instead of maximizing value, we count ways to fill capacity exactly.
The core insight is that if dp[i] represents the number of ways to make amount i, then for any coin c, adding one instance of c transforms a valid way to make (i - c) into a valid way to make i.
Crucially, we must iterate through coins in the outer loop and amounts in the inner loop. If we swapped these (outer loop amounts), we would count permutations because for amount 5 with coins [1,2], we might reach it via coin 1 then coin 2 differently than vice versa depending on when they are processed. By fixing a “current coin” and updating all reachable states using only that current coin type before moving to the next, we ensure each combination is counted exactly once per unique set of counts for each denomination.
Approach
We use Dynamic Programming with a 1D array dp where dp[i] stores the number of ways to make amount i.
- Initialize
dp[0] = 1: There is one way to make an amount of zero (by choosing no coins). All other entries start at 0. - Iterate through each coin in the input list (
for c in coins). This outer loop order enforces that we consider combinations based on specific denominations sequentially, preventing permutation counting. - For each coin
c, iterate fromi = ctoamount. - Update state:
dp[i] += dp[i - c]. We add the number of ways to make(i-c)using previous coins (including current) plus one instance ofc. - Return
dp[amount].
Complexity Analysis
- Time: . We visit each cell in our DP table once for every coin type. Given constraints (, coins ), this is roughly operations, which fits comfortably within time limits (typically ~1 second).
- Space: . We use a single array of size
amount + 1.
Solution
def change(amount: int, coins: list[int]) -> int:
# dp[i] will store the number of combinations to make amount i
# Initialize with 0s. Base case is that there's one way to make 0 (empty set).
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:
# Iterate from 'coin' up to 'amount'.
# We start at 'coin' because we can't use a coin larger than the current amount.
# This order ensures combinations are counted, not permutations.
for i in range(coin, amount + 1):
dp[i] += dp[i - coin]
return dp[amount]
Edge Cases Handled
- Amount = 0: The code initializes
dpwith size 1 (if amount is 0). Loop logic handles it correctly returningdp[0]=1. Note: Some problem variations expect 0 for this case, but standard DP returns 1. Given constraints , the array allocation works safely. - Coins = []: The outer loop over coins does not execute. Returns
dp[amount]which is initialized to 0 (unless amount was 0). Correctly handles impossible sums with no denominations. - Amount < min(coin): Inner loops range from coin to amount, so if
coin > amount, the inner loop never runs for that specific iteration of outer loop. Returns 0 correctly.