Coin change II
GoogleThe problem
Give an array coins of n integers representing coin denominations. Your task is to find the number of distinct combinations that sum up to a specified amount of money. If it's impossible to achieve the exact amount with any combination of coins, return 0. Single coin can be used any number of times. Return your answer with modulo 109+7.
Input: coins = [2, 4,10], amount = 10
Output: 4
Explanation: The four combinations are: 10 = 10 10 = 4 + 4 + 2 10 = 4 + 2 + 2 + 2 10 = 2 + 2 + 2 + 2 + 2
Input: coins = [5], amount = 5
Output: 1
Explanation: There is one combination: 5 = 5.
Input: coins = [1, 2, 3, 5], amount = 5
- 1 <= n, coins[i], amount <= 103
- All the values of **coins **are unique.
cpp
class Solution {
public:
int count(vector<int>&coins, int N, int amount) {
}
};java
class Solution {
public int count(int[] coins, int N, int amount) {
}
}python
class Solution:
def count(self, coins, N, amount):javascript
class Solution {
count(coins, N, amount) {
}
}csharp
class Solution
{
public int count(int[] coins, int N, int amount)
{
}
}go
func count(coins []int, N int, amount int) int {
}Stuck? Show a way to structure it+
- 01Set dp[0]=1 as the one way to form zero.
- 02Process coin denominations in the outer loop.
- 03For each coin, update amounts from coin through target.
- 04Add dp[amount-coin] into dp[amount], applying modulo if required.
Reference answer
Then expect these follow-ups
How would you find the minimum number of coins instead?
Tests: DP variant
How would you count ordered sequences?
Tests: loop-order semantics
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question