Coin Change 2
Problem
Given an integer amount and a list of coin denominations, return the number of combinations that make up the amount. You may assume that you have an infinite number of each kind of coin.
- 0 ≤ amount ≤ 5000
- 1 ≤ coins.length ≤ 500
- 1 ≤ coins[i] ≤ 5000
- All the values of coins are unique.
Example
amount = 5, coins = [1, 2, 5]4The four combinations are: [1,1,1,1,1], [1,1,1,2], [1,2,2], and [5]. The algorithm explores two choices at each step: include the current coin (and stay at the same coin index) or skip it (move to the next coin). Memoization caches results for subproblems defined by the current coin index and accumulated amount, preventing redundant computations. For example, when considering coin 1 at amount 0, the algorithm recursively counts all combinations that sum to 5 by including or excluding coin 1, then moves on to coin 2 and so forth, accumulating counts efficiently.
Approach
Straightforward Solution
A brute-force recursive approach tries all possible combinations by exploring every coin at every step without caching, leading to exponential time complexity due to repeated subproblems.
Core Observation
The problem asks for the count of combinations to reach a target sum using unlimited coins, which naturally breaks down into overlapping subproblems defined by the current coin index and the current accumulated amount.
Path to Optimal
PreviewRecognizing overlapping subproblems and optimal substructure suggests dynamic programming. By defining a state as (coin index, current amount), the problem can be solved recursively with memoization…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewImplement a top-down recursive function with memoization that returns the number of combinations to reach the target amount starting from a given coin index and current accumulated amount. The base cases handle exact matches (return 1) and invalid states (return 0)…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n * amount)
There are n coins and amount+1 possible accumulated amounts, resulting in O(n * amount) unique states. Each state is computed once and cached, so the total time is proportional to the number of states.
Space
O(n * amount)
The memoization dictionary stores results for each unique state (coin index, accumulated amount), requiring O(n * amount) auxiliary space. The recursion stack depth is at most n + amount in the worst case, but this is dominated by the memoization storage.
Pattern Spotlight
Dynamic Programming (Top-Down Memoization for Combinatorial Counting)
When counting combinations with choices that can be repeated unlimited times, model the problem as a state defined by the current position and accumulated value, and use recursion with memoization to avoid redundant exploration of identical subproblems.
Solution
| 1 | class Solution:
|
| 2 | def change(self, amount: int, coins: list[int]) -> int:
|
| 3 | memo = {}
|
| 4 |
|
| 5 | def dp(i, a):
|
| 6 | if a == amount:
|
| 7 | return 1
|
| 8 | if a > amount or i == len(coins):
|
| 9 | return 0
|
| 10 | if (i, a) in memo:
|
| 11 | return memo[(i, a)]
|
| 12 |
|
| 13 | memo[(i, a)] = dp(i, a + coins[i]) + dp(i + 1, a)
|
| 14 | return memo[(i, a)]
|
| 15 |
|
| 16 | return dp(0, 0) |
Step-by-Step Solution
Initialize Memoization Cache for Subproblem Results
| 3 | memo = {}
|
Objective
To create a dictionary that caches the number of combinations for each state defined by (coin index, accumulated amount).
Key Insight
Memoization prevents redundant recursive calls by storing results of subproblems. Since the problem has overlapping subproblems characterized by the current coin index and accumulated amount, caching these results ensures each unique state is computed once, drastically improving efficiency from exponential to polynomial time.
Interview Quick-Check
Core Logic
Memoization stores results keyed by (coin index, accumulated amount), enabling O(1) retrieval and avoiding recomputation.
Common Pitfalls & Bugs
Failing to memoize leads to exponential time due to repeated exploration of identical states.
Recursively Count Combinations by Including or Skipping Current Coin
To compute the number of ways to reach the target amount by either including the current coin or skipping it, using recursion with memoization.
Return Final Count from Initial State
To start the recursive counting process from the first coin and zero accumulated amount, returning the total number of combinations.
2 more steps with full analysis available on Pro.
Line Analysis
This solution has 5 Critical lines interviewers watch for.
if (i, a) in memo:Check if the current state (i, a) has been computed before.
This memoization lookup prevents recomputation of identical subproblems, drastically improving efficiency.
return memo[(i, a)]Return the cached result for the current state.
Returning the cached value avoids redundant recursion and ensures each state is computed once.
memo[(i, a)] = dp(i, a + coins[i]) + dp(i + 1, a)Compute the number of combinations by including the current coin and by skipping it, then store the sum in the memo.
This line embodies the core DP recurrence: the total combinations from the current state equal the sum of combinations including the current coin (which allows repeated use) and combinations excluding it (moving to the next coin), capturing all unique combinations without duplication.
Full line-by-line criticality + rationale for all 11 lines available on Pro.
Test Your Understanding
Why does the recursive function consider both including the current coin and moving to the next coin, rather than just one of these choices?
See the answer with Pro.
Related Problems
Dynamic Programming pattern
Don't just read it. Drill it.
Reconstruct Coin Change 2 from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Coin Change 2 drill