Difficulty: Medium2-D Dynamic Programming

Coin Change II

Problem in Plain English

Given coin denominations with unlimited supply and a target amount, count how many different combinations of coins add up to exactly that amount, where order does not matter.

Problem Statement

You are given an integer array coins of different denominations and an integer amount. Return the number of combinations that make up exactly that amount, using any number of each coin including zero.

Combinations ignore order: 2 + 2 + 1 and 1 + 2 + 2 are the same combination and must be counted once. If nothing adds up to amount, return 0.

There is exactly one way to make amount 0: use no coins at all.

Constraints

1 <= coins.length <= 300
1 <= coins[i] <= 5000
All the values of coins are unique.
0 <= amount <= 5000
The answer is guaranteed to fit into a signed 32-bit integer.

Examples

Example 1

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

There are four quantity choices: five 1s; three 1s and one 2; one 1 and two 2s; or one 5. Rearranging the same coins does not create another combination.

Example 2

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

Any number of 2-valued coins gives an even total. The odd target 3 cannot be reached, so there are zero combinations.

Example 3

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

Exactly one 10-valued coin makes 10. Zero coins give 0 and two coins give 20, so there is exactly one combination.

Example 4

Input: amount = 0, coins = [2, 5]
Output: 1

Choosing zero copies of every denomination is one valid empty combination. No positive coin can participate in an amount of zero.

Example 5

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

The combinations are three 1s and one 2 with one 1. The input need not be sorted: 2+1 and 1+2 still describe the same quantity choices.

Intuition

A combination is determined by how many copies of each denomination it uses, not by their order. For amount 5 with [1, 2, 5], the quantities are (5,0,0), (3,1,0), (1,2,0), and (0,0,1). Fixing denominations in the input order gives each quantity vector one path. Dynamic programming shares the work for smaller amounts while retaining that coin-order rule; it counts combinations rather than arrangements.

Approaches

Recursive Enumeration

Solution Details

Reveal Recursive Enumeration: intuition, complexity, and code

Intuition

Choose a quantity for the current denomination, then recurse on the next denomination with the leftover amount. For coin 1 at target 5, try quantities 0 through 5. Each branch fixes that quantity permanently, which prevents reordered duplicates. This deliberately repeats subproblems, but recursion depth is only the number of denominations rather than the target amount.

Step-by-Step Logic

Define ways(i, rest) as the number of completions using denominations from index i onward. If rest is zero, return 1 for the empty completion; if all denominations are exhausted with a positive remainder, return 0.
For the current coin, try every quantity from zero through floor(rest / coin). Recurse at i + 1 with rest - quantity * coin and sum the returned counts. Example 1 starts at (0,5) and tries zero through five copies of coin 1.
For zero 1s, the remainder 5 can be completed only by one 5. For one 1, remainder 4 can be completed by two 2s. For two 1s, remainder 3 has no completion using [2,5].
For three 1s, remainder 2 can be completed by one 2. For four 1s, remainder 1 is unreachable. For five 1s, remainder zero returns 1 immediately.
Sum those branch counts: 1 + 1 + 0 + 1 + 0 + 1 = 4. The traversal never sorts or mutates the input.

Why It Works

Every valid combination has a unique quantity of the current coin between zero and floor(rest / coin). These quantity branches are disjoint and cover every possibility. After fixing that quantity, the recursive suffix counts exactly the completions using later denominations, by induction on the remaining coin indices. A zero remainder has exactly one completion, and a positive remainder without denominations has none. Summing the disjoint branches therefore counts each complete quantity vector once. Positive denominations make every choice finite; advancing the coin index bounds stack depth by the number of denominations.

Dry Run

Recursive Enumeration: variable states at each step
Copies of 1	Rest at coin 2	Copies of 2	Rest at coin 5	Return from coin 5 / base	Running total at root after branch
0	5	0	5	quantities 0,1 return 0,1: total 1	pending
0	5	1	3	quantity 0 returns 0	pending
0	5	2	1	quantity 0 returns 0; coin-2 subtotal 1	1
1	4	0	4	quantity 0 returns 0	pending
1	4	1	2	quantity 0 returns 0	pending
1	4	2	0	zero remainder returns 1; coin-2 subtotal 1	2
2	3	0	3	quantity 0 returns 0	pending
2	3	1	1	quantity 0 returns 0; coin-2 subtotal 0	2
3	2	0	2	quantity 0 returns 0	pending
3	2	1	0	zero remainder returns 1; coin-2 subtotal 1	3
4	1	0	1	quantity 0 returns 0; coin-2 subtotal 0	3
5	0	none	none	zero remainder returns 1 immediately	4; return 4

Complexity Analysis

Time Complexity

O(n(A+1)^n)

Space Complexity

O(n)

Let n be the number of denominations and A the target amount. Each level has at most A+1 quantity choices and depth at most n; bounding every level by the last gives this loose exponential upper bound, including A=0. There is no memo table: O(n) stack frames hold only counters and subtotals. The early zero-remainder base makes A=0 constant time. The method is instructional and impractical on general maximum inputs. Each reachable subtree completes a fixed prefix of coin quantities, so its count cannot exceed the guaranteed 32-bit final count. Inputs are not copied or mutated.

Code

Solution.java

1class Solution {2    public int change(int amount, int[] coins) {3        return ways(0, amount, coins);4    }5
6    private int ways(int i, int rest, int[] coins) {7        if (rest == 0) return 1;8        if (i == coins.length) return 0;9        int total = 0;10        // Fix this coin's quantity once; later calls cannot reorder it.11        for (int count = 0; count <= rest / coins[i]; count++) {12            total += ways(i + 1, rest - count * coins[i], coins);13        }14        return total;15    }16}

Hints

Hint 1

Represent a combination by the quantity of each denomination. Which choice must be fixed to avoid counting rearrangements?

Hint 2

For a fixed coin, divide combinations into those using zero copies and those using at least one copy. Removing one copy connects the latter group to a smaller amount.

Hint 3

Use coins in the outer loop, start dp[0] at 1, and sweep amounts upward. This preserves both the denomination restriction and unlimited reuse.

Edge Cases

Amount zero has one empty combination even when every denomination exceeds the target.
An unreachable amount such as 3 with [2] returns zero; all-even denominations cannot make an odd amount.
Unsorted denominations such as [2,1] work without sorting. Denominations are unique by contract, so duplicated inputs need not be supported.
A coin larger than the target contributes no updates. One denomination dividing the target has exactly one combination, regardless of how many copies are needed.
Intermediate amounts can have huge counts while the final answer is zero: many even denominations with an odd target require overflow-safe table arithmetic.

Common Mistakes and Interview Tips

Putting amounts in the outer loop allows every denomination at each last step and counts permutations such as 1+2 and 2+1 separately.
Sweeping amounts downward treats each denomination as available once, as in 0/1 knapsack; this problem permits unlimited copies.
Initializing dp[0] to zero removes the empty-combination seed and makes all counts stay zero. In recursion, test the zero remainder before exhausted denominations.
Using only a remainder in a memoized recurrence loses which denominations are allowed. The recursive state needs both index and remainder.
Assuming the final 32-bit guarantee bounds every intermediate table cell can overflow Java int or lose JavaScript precision. Cap nonnegative counts with a proof, or use exact large integers.
Interview tip: explain the coin-prefix invariant and why ascending updates reuse the current coin. Quantity enumeration also avoids an amount-deep recursive stack, but remains exponential.

Key Takeaway

For unlimited-use combination counting, fix an item order and process one denomination completely before the next. The coin-prefix invariant removes reordered duplicates, while ascending capacity updates allow repeated use. Changing either loop order or traversal direction changes what the table counts.