Search⌘ K
AI Features
Home
Courses
Algorithms for Coding Interviews in Java

Solution: Coin Change Problem

Understand different approaches to solve the coin change problem, including brute force, memoization, tabularization, and optimized solutions. Learn how dynamic programming improves efficiency by reducing repeated computations and how space optimization can further enhance the solution.

We'll cover the following...

Solution #1: Brute force

Java
class Count {
 public static int countChange(int[] denoms, int denomsLength, int amount) {
  // If n is 0 then there is 1 solution  
  // (do not include any coin) 
  if (amount == 0)
   return 1;
  // If n is less than 0 then no  
  // solution exists 
  if (amount < 0 || denomsLength <= 0)
   return 0;
  // If there are no coins and n  
  // is greater than 0, then no 
  // solution exist 
  if (denomsLength <= 0 && amount >= 1)
   return 0;
  // count is sum of solutions (i)  
  // including S[m-1] (ii) excluding S[m-1] 
  return countChange(denoms, denomsLength - 1, amount) + countChange(denoms, denomsLength, amount - denoms[denomsLength - 1]);
 }
 public static void main(String args[]) {
  // Denominations: quarters (25 cents), dimes (10 cents), nickels (5 cents), and pennies (1 cent)
  int[] denoms = {
   25,
   10,
   5,
   1
  };
  System.out.println(countChange(denoms, 4, 10));
 }
};

Explanation

To count the total number of solutions, we divide the solution into two sets: one subset does not contain the coin currently being evaluated, and the other subset contains at least one coin of that denomination.

However, notice that the function above recomputes the same subproblem several times.

Time complexity

The time complexity of this solution is in O(2denomsLength)O(2^{denomsLength}). Why? Because for every coin, we have 2 options: to either include it or exclude it. So, if we think in terms of binary, it’s 0 to exclude or 1 to include every coin. For example, if we have 2 coins, the options will be 00, 01, 10, 11, which is 4 or 222^2 options. Therefore, extrapolating to nn ...