Difficulty: Medium · LeetCode 518

Problem

Count the number of combinations to make an amount using given coin denominations (unlimited supply).

Understanding the problem

Unbounded Knapsack combinations! Outer loop must iterate coins first to avoid counting permutations twice (e.g. 1+2 vs 2+1).

Intuition

dp[c] += dp[c - coin]. Outer loop iterating coins ensures ordering is fixed and combinations are counted.

Approach

Initialize dp = [0] * (amount + 1) and dp[0] = 1.
For coin in coins: for current from coin to amount: dp[current] += dp[current - coin].
Return dp[amount].

Naive Solution — Recursion

Try taking or skipping each coin recursively.

Python

class Solution:
    def change(self, amount, coins):

        def dfs(index, remaining):
            if remaining == 0:
                return 1

            if index == len(coins) or remaining < 0:
                return 0

            # Use current coin
            use = dfs(
                index,
                remaining - coins[index]
            )

            # Skip current coin
            skip = dfs(
                index + 1,
                remaining
            )

            return use + skip

        return dfs(0, amount)

C++

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        return dfs(coins, 0, amount);
    }

private:
    int dfs(vector<int>& coins, int index, int remaining) {
        if (remaining == 0) return 1;
        if (index == (int)coins.size() || remaining < 0) return 0;

        // Use current coin
        int use = dfs(coins, index, remaining - coins[index]);

        // Skip current coin
        int skip = dfs(coins, index + 1, remaining);

        return use + skip;
    }
};

Java

class Solution {
    public int change(int amount, int[] coins) {
        return dfs(coins, 0, amount);
    }

    private int dfs(int[] coins, int index, int remaining) {
        if (remaining == 0) return 1;
        if (index == coins.length || remaining < 0) return 0;

        // Use current coin
        int use = dfs(coins, index, remaining - coins[index]);

        // Skip current coin
        int skip = dfs(coins, index + 1, remaining);

        return use + skip;
    }
}

JavaScript

var change = function(amount, coins) {
    const dfs = (index, remaining) => {
        if (remaining === 0) return 1;
        if (index === coins.length || remaining < 0) return 0;

        // Use current coin
        const use = dfs(index, remaining - coins[index]);

        // Skip current coin
        const skip = dfs(index + 1, remaining);

        return use + skip;
    };

    return dfs(0, amount);
};

Time: Exponential · Aux Space: O(amount + n)

Optimized Code (Python 3)

Python

class Solution:
    def change(self, amount, coins):

        dp = [0] * (amount + 1)
        dp[0] = 1

        for coin in coins:
            for current in range(
                coin,
                amount + 1
            ):
                dp[current] += dp[current - coin]

        return dp[amount]

C++

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        // unsigned: unrelated cells may overflow, but dp[amount] always fits
        vector<unsigned long long> dp(amount + 1, 0);
        dp[0] = 1;

        for (int coin : coins) {
            for (int current = coin; current <= amount; current++) {
                dp[current] += dp[current - coin];
            }
        }

        return (int)dp[amount];
    }
};

Java

class Solution {
    public int change(int amount, int[] coins) {
        long[] dp = new long[amount + 1];
        dp[0] = 1;

        for (int coin : coins) {
            for (int current = coin; current <= amount; current++) {
                dp[current] += dp[current - coin];
            }
        }

        return (int) dp[amount];
    }
}

JavaScript

var change = function(amount, coins) {
    const dp = new Array(amount + 1).fill(0);
    dp[0] = 1;

    for (const coin of coins) {
        for (let current = coin; current <= amount; current++) {
            dp[current] += dp[current - coin];
        }
    }

    return dp[amount];
};

Time: O(amount × n) · Space: O(amount)

Takeaway

Unbounded Knapsack Combinations — Outer loop over coins, inner loop increasing order over amount.