Solution: Coin Change Problem

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));
 }
};