Coin Change II
Problem Description
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 1:
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
Example 2:
Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.
Example 3:
Input: amount = 10, coins = [10]
Output: 1
Constraints:
1 <= coins.length <= 3001 <= coins[i] <= 5000- All the values of
coinsare unique. 0 <= amount <= 5000
Solve it on LeetCode
Approaches
Approach 1: Recursion
Intuition:
Use recursion to explore all possible ways to make up the amount using combinations of the coins. The idea is to traverse each coin and either take it (reduce the amount) or skip it and move to the next coin. This basic approach generates all combinations but is not efficient due to repeated computations.
Code:
- Time Complexity: O(2^n), where n is the number of coins. This is because each coin can be taken or not, leading to a binary decision at each step.
- Space Complexity: O(n), due to the recursion stack.
2. Dynamic Programming - 2D Array
Intuition:
To avoid the repetition in the recursive approach, use a 2D DP table. Here, dp[i][j] represents the number of ways to get the amount j using first i coin types. The table is filled in a bottom-up manner.
Code:
- Time Complexity: O(n * amount), where n is the number of coins.
- Space Complexity: O(n * amount), for storing the entire DP table.
3. Dynamic Programming - 1D Array
Intuition:
Further optimize the space usage by using a 1D DP array. Instead of maintaining a 2D array, keep track of number of ways to achieve different sums using a single 1D DP array. Here, dp[j] represents the number of ways to get the amount j.
Code:
- Time Complexity: O(n * amount), where n is the number of coins.
- Space Complexity: O(amount), optimal space usage with a 1D array.