Coin Change

Introduction

Given an infinite supply of ‘n’ coin denominations and a total money amount, we are asked to find the total number of distinct ways to make up that amount.

Example:

Denominations: {1,2,3}
Total amount: 5
Output: 5
Explanation: There are five ways to make the change for '5', here are those ways:
  1. {1,1,1,1,1} 
  2. {1,1,1,2} 
  3. {1,2,2}
  4. {1,1,3}
  5. {2,3}

Problem Statement

Given a number array to represent different coin denominations and a total amount 'T', we need to find all the different ways to make a change for 'T' with the given coin denominations. We can assume an infinite supply of coins, therefore, each coin can be chosen multiple times.

Constraints:

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 2³¹ - 1
• 0 <= amount <= 10⁴

Try it yourself

Try solving this question here:

🎯 STRICT STANDOUT — Coin Change

0. Pattern family

Family: Unbounded knapsack DP (ways or min coins — confirm page)

1. Why / judgment (K3)

Company-practice Coin Change concept: unbounded knapsack family. Two famous twins: (1) fewest coins for amount (LeetCode 322) — min DP; (2) number of combinations (518 / educative ways) — count DP. Outer coins inner amount → combinations; reverse → permutations. Why DP: optimal substructure on remaining amount; overlapping subproblems.

2. Worked complexity / derivation (K11)

Min-coins: dp[x]=min over c of dp[x-c]+1; O(amount·|coins|) time, O(amount) space.
Ways: dp[x]+=dp[x-c]; same complexity. amount=10^4, coins≤12 typical interview bounds.

3. Pattern + recognition + when-NOT (K12)

Name: UNBOUNDED KNAPSACK / COIN DP

Recognition: unlimited supply; target sum; min count OR number of combinations.

When-NOT: 0/1 each coin once → 0/1 knapsack. Need actual set → reconstruct. Greedy only if canonical coin system (US coins often) — not general.

4. Edge hand-run (K13)

amount 0 → 0 coins / 1 way empty. No solution min → -1; ways → 0. coins=[2] amount=3 → impossible.

5. Interviewer follow-ups & drills

Q1. Greedy fail example?
Model answer: coins=1,3,4 amount=6: greedy 4+1+1=3 vs optimal 3+3=2.

Q2. Loop order for combinations?
Model answer: coins outer, amount inner.

Q3. Min vs ways init?
Model answer: min: inf except 0; ways: 1 at 0.

I just read a lesson on **Coin Change** (DSA) and want to truly understand it. Explain Coin Change from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Teach me **Coin Change** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Quiz me on **Coin Change** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Help me remember **Coin Change** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.