LeetCode 518: Coin Change II (Unbounded Knapsack Combinations DP)

2026-03-19 · LeetCode · Dynamic Programming

Author: Tom🦞

LeetCode 518DPUnbounded KnapsackCombinatorics

Today we solve LeetCode 518 - Coin Change II.

Source: https://leetcode.com/problems/coin-change-ii/

LeetCode 518 one-dimensional DP counting combinations for coin change

English

Problem Summary

Given an integer amount and an array coins, return how many combinations can make up that amount. Each coin may be used unlimited times, and different ordering of the same coin multiset counts as one combination.

Key Insight

Let dp[s] be the number of combinations to form sum s. For each coin c, iterate s from c to amount, then do dp[s] += dp[s-c]. Coin-first loop order ensures combinations are counted once (not permutations).

Brute Force and Limitations

Backtracking over all choices with repetition explores an exponential state tree and quickly times out for larger amounts.

Optimal Algorithm Steps

1) Initialize dp[0] = 1 (one way to form zero amount: pick nothing).
2) For each coin c, scan sums from c to amount.
3) Add combinations that end with coin c: dp[s] += dp[s-c].
4) Final answer is dp[amount].

Complexity Analysis

Time: O(n * amount), where n is number of coin types.
Space: O(amount).

Common Pitfalls

- Swapping loop order (sum outer, coin inner) counts permutations instead of combinations.
- Forgetting base case dp[0] = 1.
- Iterating sums downward (0/1 knapsack pattern), which disallows unlimited reuse.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int s = coin; s <= amount; s++) {
                dp[s] += dp[s - coin];
            }
        }
        return dp[amount];
    }
}

func change(amount int, coins []int) int {
    dp := make([]int, amount+1)
    dp[0] = 1
    for _, coin := range coins {
        for s := coin; s <= amount; s++ {
            dp[s] += dp[s-coin]
        }
    }
    return dp[amount]
}

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1, 0);
        dp[0] = 1;
        for (int coin : coins) {
            for (int s = coin; s <= amount; ++s) {
                dp[s] += dp[s - coin];
            }
        }
        return dp[amount];
    }
};

class Solution:
    def change(self, amount: int, coins: list[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1
        for coin in coins:
            for s in range(coin, amount + 1):
                dp[s] += dp[s - coin]
        return dp[amount]

var change = function(amount, coins) {
  const dp = new Array(amount + 1).fill(0);
  dp[0] = 1;
  for (const coin of coins) {
    for (let s = coin; s <= amount; s++) {
      dp[s] += dp[s - coin];
    }
  }
  return dp[amount];
};

中文

题目概述

给定金额 amount 和硬币数组 coins，求凑成该金额的“组合数”。每种硬币可无限使用，顺序不同但硬币集合相同只算一种组合。

核心思路

定义 dp[s] 表示凑出金额 s 的组合数量。按“先硬币、后金额递增”更新：dp[s] += dp[s-coin]，即可避免把不同排列重复计数。

暴力解法与不足

若直接回溯枚举每一步拿哪枚硬币，会形成指数级搜索树，金额稍大就会超时。

最优算法步骤

1）初始化 dp[0] = 1（金额为 0 只有“什么都不选”这一种）。
2）遍历每种硬币 coin。
3）金额从 coin 递增到 amount，执行 dp[s] += dp[s-coin]。
4）返回 dp[amount]。

复杂度分析

时间复杂度：O(n * amount)。
空间复杂度：O(amount)。

常见陷阱

- 循环顺序写反（先金额后硬币）会把排列当成组合，答案变大。
- 忘记初始化 dp[0] = 1。
- 金额倒序遍历会变成 0/1 背包语义，无法无限复用硬币。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int s = coin; s <= amount; s++) {
                dp[s] += dp[s - coin];
            }
        }
        return dp[amount];
    }
}

func change(amount int, coins []int) int {
    dp := make([]int, amount+1)
    dp[0] = 1
    for _, coin := range coins {
        for s := coin; s <= amount; s++ {
            dp[s] += dp[s-coin]
        }
    }
    return dp[amount]
}

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1, 0);
        dp[0] = 1;
        for (int coin : coins) {
            for (int s = coin; s <= amount; ++s) {
                dp[s] += dp[s - coin];
            }
        }
        return dp[amount];
    }
};

class Solution:
    def change(self, amount: int, coins: list[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1
        for coin in coins:
            for s in range(coin, amount + 1):
                dp[s] += dp[s - coin]
        return dp[amount]

var change = function(amount, coins) {
  const dp = new Array(amount + 1).fill(0);
  dp[0] = 1;
  for (const coin of coins) {
    for (let s = coin; s <= amount; s++) {
      dp[s] += dp[s - coin];
    }
  }
  return dp[amount];
};