# Coin Change 2 Leetcode Solution

Difficulty Level Medium
Array Dynamic Programming Goldmann SachsViews 3095

## Problem Statement

The Coin Change 2 LeetCode Solution – “Coin Change 2” states that given an array of distinct integers `coins` and an integer `amount`, representing a total amount of money.

We need to return the count of the total number of different possible combinations that sum to the `amount`.  Note that there are an infinite number of coins of each type.

## Example:

`Input:  amount = 5, coins = [1,2,5]`
`Output: 4`

Explanation:

• All possible combinations that sum to 5 are: [, [2,2,1], [2,1,1,1], [1,1,1,1,1]].
`Input:  amount = 3, coins = `
`Output:0`

Explanation:

• There doesn’t exist any combination that sums to 3.

## Approach

Let dp[i][j] be the number of combos to make amount i using the first j coins.

Base Case: dp[j] = 0 for all j because there is always one way to make 0 coins. Recursive Case: To make amount i, we either use the jth coin or we don’t. The total number of combos to make amount i is the sum of the two cases.

– Case 1, don’t use coin j: We don’t use coin j but we can still use the remaining j-1 coins. There are dp[i][j-1] combos to make amount i using the first j-1 coins.

– Case 2, use coin j: Let the jth coin be c. We make the current amount by adding c to the previous amount. Since the previous amount is i – c then there are dp[i-c][j] combos to make amount i using the first j coins.

The answer is the number of ways to make the target amount using all the coins, dp[amount][coins.size()]

### Idea:

1. The main idea to solve this problem is to use dynamic programming.
2. Let’s dp[i] = the total number of combinations whose sum is equal to i.
3. Base Case: dp = 1.
4. Now, for every coin x, iterate in the linear dp array and for each i, add dp[i-x] to dp[i] since we can reach i state from (i-x) state.
5. Finally, return dp[amount] which is our answer. ## Code

### C++ Solution:

```class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<int> dp(amount+1);
dp = 1;
for(auto& x:coins){
for(int i=x;i<=amount;i++){
dp[i] += dp[i-x];
}
}
return dp[amount];
}
};```

### Java Solution:

```class Solution {
public int change(int amount, int[] coins) {
int dp[] = new int[amount+1];
for(int i=0;i<=amount;i++){
dp[i] = 0;
}
dp = 1;
for(int i=0;i<coins.length;i++){
for(int j=coins[i];j<=amount;j++){
dp[j] += dp[j-coins[i]];
}
}
return dp[amount];
}
}```

## Complexity Analysis for Coin Change 2 Leetcode Solution

### Time Complexity

The time complexity of the above code is O(N*amount) since, for each coin, we are iterating for the amount number of times.

### Space Complexity

The space complexity of the above code is O(amount)since we’re creating a linear dynamic programming array of size amount.

Translate »