Problem Statement
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money. Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.
You may assume that you have an infinite number of each kind of coin. The answer is guaranteed to fit into a signed 32-bit integer.
Example Inputs and Outputs
-
Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: There are four ways to make up the amount:
- 5 = 5
- 5 = 2 + 2 + 1
- 5 = 2 + 1 + 1 + 1
- 5 = 1 + 1 + 1 + 1 + 1
-
Input: amount = 3, coins = [2]
Output: 0
Explanation: The amount of 3 cannot be made up with coins of denomination 2.
-
Input: amount = 10, coins = [10]
Output: 1
Explanation: The only combination is 10 = 10.
Approach
Dynamic Programming (Optimized Solution)
Steps
- Use recursion with memoization to solve the problem.
- Define a helper function
f(idx, coins, amount, dp) where:
idx represents the current index of the coin array.amount is the remaining target amount.dp is a 2D memoization table.
- Base cases:
- If
idx == 0:
- If
amount == 0, return 1 (one way to make zero).
- If
amount % coins[0] == 0, return 1.
- Otherwise, return
0.
- If
amount == 0, return 1 (one way to make zero).
- Use memoization to avoid redundant computations.
- Combine results for picking and not picking the current coin.
- Return the result stored in
dp.
Code Snippet
Dry Run
Input: amount = 5, coins = [1, 2, 5]
- Initialize a 2D
dp array with dimensions [n][amount + 1] filled with -1.
- Recursive calls explore all possibilities for each coin and target amount.
- Base case handles edge scenarios like
idx = 0 or amount = 0.
Complexity Analysis
- Time Complexity:
O(n * amount) where n is the number of coins and amount is the target value.
- Space Complexity:
O(n * amount) due to the memoization table.
Conclusion
This guide demonstrates how to use recursion with memoization (dynamic programming) to solve the coin change combination problem efficiently. The approach eliminates redundant calculations, ensuring optimal performance. By breaking the problem into smaller subproblems, we efficiently compute the total number of combinations. This methodology is a powerful tool for solving problems involving combinations and permutations.