Coin Change 2 Leetcode Solution

Difficulty Level Medium
Frequently asked in Adobe Amazon Apple Bloomberg ByteDance Cisco Citadel Facebook Google Microsoft TCS Uber
Array Dynamic Programming Goldmann SachsViews 4432

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: [[5], [2,2,1], [2,1,1,1], [1,1,1,1,1]].
Input:  amount = 3, coins = [2]
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[0][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[0] = 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.

Coin Change 2 Leetcode Solution

Code

C++ Solution:

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount+1);
        dp[0] = 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[0] = 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 »