Coin Change Editorial

Practice Problem Link: Practice Problem | Coin Change

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

You are given coins of different denominations, represented by an array - coins of size n. You are also given a value - target. Find the different number of combinations that make up the amount target. Assume that you have an infinite number of each kind of coin.

Naive Approach

We can solve this problem naively by using a brute force recursion. We can try all possible combinations of taking coins to add up to the target amount and add them up to get the number of ways of attaining the target amount. The base case would be the cases when we have zero coins, or if the target to be attained is zero.

Analysis 

• Time Complexity: O(targetⁿ) // Exponential
• Space Complexity: O(targetⁿ) // Exponential

Implementation

C++

int coinChange(vector<int> &coins, int n, int target) {
   if(target == 0) {
       return 1;
   }
   if(target < 0) {
       return 0;
   }
   if(n <= 0  && target > 0) {
       return 0;
   }
   return coinChange(coins, n - 1, target) + coinChange(coins, n, target - coins[n - 1]);
}
int numberOfCombinations(vector<int> &coins, int target) {
   int n = coins.size();
   return coinChange(coins, n, target);
}

Java

class Solution {
   int coinChange(int[] coins, int n, int target) {
       if(target == 0) {
           return 1;
       }
       if(target < 0) {
           return 0;
       }
       if(n <= 0  && target > 0) {
           return 0;
       }
       return coinChange(coins, n - 1, target) + coinChange(coins, n, target - coins[n - 1]);
   }
   int numberOfCombinations(int[] coins, int target) {
       int n = coins.length;
       return coinChange(coins, n, target);
   }
}

Optimal Approach

We can solve this problem in pseudo-polynomial time by Dynamic Programming. Observe that many of the recursive calls the coinChange() function makes are for the same parameter. So, we memoize the function calls using a DP array so that the same function call is not made again and again. Here, in our DP array, DP[i][j] will represent the number of ways we can attain target sum j using 1st i denominations given.

Analysis

• Time Complexity: O(n * target)
• Space Complexity: O(n * target)

Implementation

C++

vector<vector<int>> dp;
int coinChange(vector<int> &coins, int n, int target) {
   if(target == 0) {
       return 1;
   }
   if(target < 0) {
       return 0;
   }
   if(n <= 0  && target > 0) {
       return 0;
   }
   if(dp[n][target] != -1) {
       return dp[n][target];
   }
   return dp[n][target] = coinChange(coins, n - 1, target) + 
   coinChange(coins, n, target - coins[n - 1]);
}
int numberOfCombinations(vector<int> &coins, int target) {
   int n = coins.size();
   vector<vector<int>> temp(n + 1, vector<int> (target + 1, -1));
   dp = temp; 
   return coinChange(coins, n, target);
}

Java

class Solution {
   int dp[][];
   int coinChange(int[] coins, int n, int target) {
       if(target == 0) {
           return 1;
       }
       if(target < 0) {
           return 0;
       }
       if(n <= 0  && target > 0) {
           return 0;
       }
       if(dp[n][target] != -1) {
           return dp[n][target];
       }
       return dp[n][target] = coinChange(coins, n - 1, target) +  
           coinChange(coins, n, target - coins[n - 1]);
   }
   int numberOfCombinations(int[] coins, int target) {
       int n = coins.length;
       dp = new int[n + 1][target + 1];
       for(int i = 0; i <= n; i++) {
           Arrays.fill(dp[i], -1);
       }
       return coinChange(coins, n, target);
   }
}

Bottom-Up Implementation

C++

int numberOfCombinations(vector<int> coins, int target) {
   int n = coins.size();
   int dp[n + 1][target + 1];
   for(int i = 0; i <= n; i++) {
       for(int j = 0; j <= target; j++) {
           if(i == 0) {
               dp[i][j] = 0;
           } else if(j == 0) {
               dp[i][j] = 1;
           } else {
               if(j - coins[i - 1] >= 0) {
                   dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]];
               } else {
                   dp[i][j] = dp[i - 1][j];
               }
           }
       }
   }
   return dp[n][target];
}

Java

class Solution {
   int numberOfCombinations(int[] coins, int target) {
       int n = coins.length;
       int[][] dp = new int[n + 1][target + 1];
       for(int i = 0; i <= n; i++) {
           for(int j = 0; j <= target; j++) {
               if(i == 0) {
                   dp[i][j] = 0;
               } else if(j == 0) {
                   dp[i][j] = 1;
               } else {
                   if(j - coins[i - 1] >= 0) {
                       dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]];
                   } else {
                       dp[i][j] = dp[i - 1][j];
                   }
               }
           }
       }
       return dp[n][target];
   }
}