Coin Change II — Count Ways Unbounded Knapsack

Problem

Return the number of combinations (not permutations) of coins that sum to amount.

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

Key Insight: Coins Outer, Amounts Inner

To count combinations (not permutations), loop over coins in outer loop. Each coin is considered only in its position relative to previously considered coins.

Time: O(amount * n) | Space: O(amount)

Solutions

Python

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

C++

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

Java

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

Complexity

Time: O(amount * n) | Space: O(amount)

Key Takeaway

Combinations → coins outer loop. Permutations → amounts outer loop. This is the classic knapsack outer/inner loop distinction.