Coin Change II

Medium Problem 131 of 151 Java and Python

Problem

You are given coin denominations coins and a total amount. Return the number of combinations that make up amount, using any number of each coin. Return 0 if it cannot be made.

Different orders of the same coins count as one combination.

Example 1

Input: amount = 5, coins = [1, 2, 5]
Output: 4
Why: 5, 2+2+1, 2+1+1+1, 1+1+1+1+1.

Example 2

Input: amount = 3, coins = [2]
Output: 0

Example 3

Input: amount = 10, coins = [10]
Output: 1

Constraints

1 ≤ coins.length ≤ 300
0 ≤ amount ≤ 5000

Explanation

Think of it as a table over (coins considered, amount). For each coin, you either never use it, or use it at least once: ways(i, a) = ways(i - 1, a) + ways(i, a - coin[i]).

In one array: loop coins on the outside and amounts on the inside. Each combination is then built in coin order and counted once. Looping amounts on the outside would count 1+2 and 2+1 separately.

Approach 1 · Naive

Recursion over coins

Time Exponential
Space O(amount) recursion

At coin i, either skip to the next coin or use coin i once more (staying on it).

count(i, remaining): 1 if remaining == 0; 0 if i is past the last coin or remaining < 0.
Return count(i + 1, remaining) + count(i, remaining - coins[i]).

Java

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

    private int count(int[] coins, int i, int remaining) {
        if (remaining == 0) {
            return 1;
        }
        if (i == coins.length || remaining < 0) {
            return 0;
        }
        return count(coins, i + 1, remaining) + count(coins, i, remaining - coins[i]);
    }
}

Python

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        def count(i, remaining):
            if remaining == 0:
                return 1
            if i == len(coins) or remaining < 0:
                return 0
            return count(i + 1, remaining) + count(i, remaining - coins[i])

        return count(0, amount)

Approach 2 · Optimal

One array, coins outside

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

ways[a] = combinations for amount a using the coins processed so far.

ways[0] = 1.
For each coin, for a from coin to amount: ways[a] += ways[a - coin].
Return ways[amount].

Java

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

Python

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

Complexity compared

Approach	Time	Space
Naive Recursion over coins	Exponential	O(amount) recursion
Optimal One array, coins outside	O(n · amount)	O(amount)

Key takeaways

Combinations: coins outer, amounts inner. Permutations (Combination Sum IV): amounts outer, coins inner.
Amounts go upwards here because each coin may be reused (unbounded knapsack).

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem