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
Recognizing 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. The key insight is to consider two choices at each state: include the current coin (stay at the same index and add its value) or exclude it (move to the next coin). Memoization ensures each state is computed once, reducing complexity drastically.
Optimal Approach
Implement 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). The final answer is obtained by calling this function starting at coin index 0 and amount 0.
Time
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
| 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)]
|
| 13 | memo[(i, a)] = dp(i, a + coins[i]) + dp(i + 1, a)
|
| 14 | return memo[(i, a)]
|
Objective
To compute the number of ways to reach the target amount by either including the current coin or skipping it, using recursion with memoization.
Key Insight
At each recursive call, the algorithm explores two paths: one that adds the current coin's value to the accumulated amount (allowing unlimited reuse of the same coin), and one that moves to the next coin without changing the amount. This dual-choice recursion captures all unique combinations. Memoization ensures that once a state is solved, its result is reused, preventing exponential blowup.
Interview Quick-Check
Core Logic
The recursive function returns the sum of counts from including the current coin (stay at same index) and skipping it (move to next index), covering all combination possibilities.
State & Boundaries
Base cases return 1 when the accumulated amount equals the target and 0 when it exceeds the target or runs out of coins.
Common Pitfalls & Bugs
Not handling base cases correctly can lead to incorrect counts or infinite recursion.
Return Final Count from Initial State
| 16 | return dp(0, 0) |
Objective
To start the recursive counting process from the first coin and zero accumulated amount, returning the total number of combinations.
Key Insight
The initial call represents the full problem: counting all combinations to reach the target amount starting with the first coin and no amount accumulated. This triggers the entire memoized recursion, which efficiently explores all valid combinations and returns the final count.
Interview Quick-Check
Core Logic
Starting recursion at (0, 0) covers all coins and amounts, ensuring the complete solution space is explored.
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.
if a == amount:Check if the accumulated amount equals the target amount.
This base case signifies a valid combination has been found, so the function returns 1 to count it.
if a > amount or i == len(coins):Check if the accumulated amount exceeds the target or if all coins have been considered.
This base case prunes invalid paths that either overshoot the target or run out of coins, returning 0 to indicate no valid combination from this state.
memo = {}Initialize a memoization dictionary to cache results of subproblems.
This cache is essential to avoid redundant recursive calls by storing the number of combinations for each unique state defined by (coin index, accumulated amount).
return dp(0, 0)Start the recursion from the first coin and zero accumulated amount.
This initial call triggers the entire memoized recursion, exploring all valid combinations to reach the target amount.
def dp(i, a):Define the recursive function dp with parameters coin index i and accumulated amount a.
This function models the problem as a state machine where each state represents the current coin and the amount accumulated so far, enabling systematic exploration of all combinations.
return 1Return 1 to count the valid combination.
Returning 1 here contributes to the total count of combinations, marking the successful end of a recursive path.
return 0Return 0 to indicate no valid combination from this state.
Returning 0 here prevents invalid paths from contributing to the count, ensuring correctness.
return memo[(i, a)]Return the computed number of combinations for the current state.
Returning the memoized result completes the recursive call, propagating the count up the call stack.
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?
Because including the current coin accounts for combinations that use it multiple times, while moving to the next coin explores combinations that exclude it. Both choices together ensure all unique combinations are counted without duplication.
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