DSA interview question

Coin Change 2 (Number of Combinations)

Hard · Algorithms · Topics: dynamic programming, unbounded knapsack

The problem

You're building the "checkout settlement" module for a vending-machine network. Each machine accepts a fixed set of coin denominations, and management wants to know, for auditing purposes, how many distinct ways a given target amount could have been paid using those denominations — not the minimum coins, but the total count of distinct combinations (where order doesn't matter — paying with a nickel-then-dime is the same combination as dime-then-nickel). Given an integer array coins (unlimited supply of each denomination) and an integer amount, return the number of combinations that make up that amount.

Function signature

int change(int amount, vector<int>& coins);

Test cases

`coins`	`amount`	Output	Explanation
`[1,2,5]`	5	4	{5}, {2,2,1}, {2,1,1,1}, {1,1,1,1,1}
`[2]`	3	0	can't make 3 using only 2s
`[1]`	0	1	exactly one way to make 0: use no coins
`[]`	5	0	no coins available, can't make positive amount
`[]`	0	1	empty coin set, but amount 0 needs zero coins — always 1 way
`[3,5,7]`	10	1	only {3,7} works
`[1,2,3]`	4	4	{1,1,1,1}, {1,1,2}, {2,2}, {1,3}

(Critical distinction to flag upfront: this counts COMBINATIONS, order-independent — different from "Coin Change 1" which asks for MINIMUM coins, and different from counting order-dependent PERMUTATIONS, which is a related-but-distinct problem.)

How interviewers phrase it

"Given coin denominations (unlimited supply) and a target amount, how many distinct combinations of coins sum to that amount?"
"In how many ways can you make change for this amount?"
Often given as a direct follow-up to "Coin Change 1" (minimum coins) specifically to test whether you notice this asks for a COUNT of combinations, not a minimum — very different transition despite similar setup.

Clarifying questions to ask

Combinations (order doesn't matter, e.g. {1,2} == {2,1}) or permutations (order matters, e.g. count 1-then-2 and 2-then-1 as distinct)? — This is THE most important clarifying question; it fundamentally changes loop nesting order.
Is each coin denomination available in unlimited supply? (Confirm — this is unbounded knapsack territory, not 0/1.)
What should be returned for amount = 0? (Standard convention: 1, representing "the empty combination.")
Are coin values guaranteed positive and distinct? Could there be duplicate values in the coins array?
Could the count overflow a 32-bit integer for large inputs? What's the expected range of amount and number of coin types?

Follow-ups to expect

"How is this different from counting PERMUTATIONS instead of combinations?"
"Can you also return the minimum number of coins needed (Coin Change 1), using similar logic?"
"Can you optimize space?"
"Can you enumerate the actual combinations, not just count them?"
"What if coins had different available quantities (bounded, not unlimited)?"
"How does this relate to the classic 'coin change counting' via generating functions?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview