Domain 2MediumCORE

Coin Change 2

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.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#FAANG asked: 1

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:

  1. 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.
  2. Infinite Supply: Each coin can be used multiple times.
  3. 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 coins list: 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.

  1. Initialize dp[0] = 1: There is one way to make an amount of zero (by choosing no coins). All other entries start at 0.
  2. 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.
  3. For each coin c, iterate from i = c to amount.
  4. 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 of c.
  5. Return dp[amount].

Complexity Analysis

  • Time: O(amount×len(coins))O(amount \times len(coins)). We visit each cell in our DP table once for every coin type. Given constraints (amount≤5000amount \le 5000, coins ≤500\le 500), this is roughly 2.5×1062.5 \times 10^6 operations, which fits comfortably within time limits (typically ~1 second).
  • Space: O(amount)O(amount). 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 dp with size 1 (if amount is 0). Loop logic handles it correctly returning dp[0]=1. Note: Some problem variations expect 0 for this case, but standard DP returns 1. Given constraints amount≥0amount \ge 0, 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.