Coin Change II

Medium20–25 min

Topics

Dynamic ProgrammingArray

Companies

AmazonGoogleGoldman Sachs

Using the same unlimited-supply cashier setup as before, this time the question isn't the fewest coins but how many genuinely different ways exist to hand over the exact amount owed. Two ways of paying count as the same if they use every denomination the same number of times — reaching for a coin before or after another one doesn't create a new way, only the final tally of each denomination used does. Because order doesn't matter, coins have to be considered in a fixed sequence to avoid counting the same combination more than once: at any point, either reuse the current coin denomination again (if it still fits within what's left) or commit to moving on and never using that denomination again. Reaching a remaining amount of exactly 0 marks one valid combination; running out of denominations before that ends the path with nothing. Adding together the combinations found by reusing the current coin and by moving on to the next one counts every distinct combination exactly once.

Test Case 1:

Input:coins = [2, 3, 5], amount = 6

Output:2

Explanation:Two combinations make 6: {2,2,2} and {3,3} — order doesn't matter, only which coins and how many of each.

Test Case 2:

Input:coins = [4, 6, 3], amount = 10

Output:2

Explanation:Two combinations make 10: {4,3,3} and {4,6}.

Test Case 3:

Input:coins = [9], amount = 5

Output:0

Explanation:9 alone always overshoots 5, so no combination of just 9s ever reaches it.

Constraints

◆1 ≤ coins.length ≤ 15
◆1 ≤ coins[i] ≤ 100
◆0 ≤ amount ≤ 1000

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Without Memoization

Brute

To avoid counting the same combination twice (using a 2 then a 3 is the same combination as a 3 then a 2), process the coin denominations in a fixed order and, at each one, decide how many times to use it before moving permanently on to the next denomination. From a given coin and remaining amount, there are two options: use this same coin again (if it still fits, lowering the remaining amount by its value) or move on to the next coin denomination entirely (leaving the remaining amount untouched). Reaching a remaining amount of exactly 0 counts as one valid combination; running out of coin denominations before that contributes nothing. Adding up the ways found by both options at every step counts every combination exactly once.

TimeO(2^amount)

SpaceO(coins.length + amount)

Java

Try it out

class Solution {
    private int[] coins;

    public int coinChangeII(int[] coins, int amount) {
        this.coins = coins;
        return solve(0, amount);
    }

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

Optimal — Bottom-Up 1D DP

Optimal

Track, for every amount from 0 up to the target, how many combinations of coins make it exactly — starting from exactly one way to make amount 0 (use no coins). Processing one coin denomination completely before moving to the next, and sweeping that coin's update forward from its own value up to the target, lets that coin be reused any number of times within its own pass while still counting each combination of denominations only once overall (since a combination is defined by how many of each coin it uses, not the order they're added in). After every coin denomination has been swept through, the entry at the target amount holds the total combination count.

TimeO(coins.length × amount)

SpaceO(amount)