Computes number ways we can represent the given amount with different combination of coin denominations

CoinChange.java

/* File:    CoinChange.java
 * Created: 2018-04-26
 * Author:  Sabbir Manandhar
 *
 * Copyright (c) 2018 WorldLingo Inc.
 */

/**
 * Number of ways given denominations can sum up a given total
 *
 * @author Sabbir Manandhar
 * @version 1.0
 */
public class CoinChange {

  /**
   * Driver Method
   *
   * @param args
   */
  public static void main(String[] args) {
    int[] coins = new int[]{1, 5, 10};
    int N = 10;
    System.out.println(count(coins, N, 0));
  } // main

  //---------------------------------------------------------------------------------------------

  /**
   * Computes the number of ways the total could be represented by denominations
   *
   * @param coins denominations available
   * @param N     target sum
   * @param index current index of denominations we are using
   * @return number of ways
   */
  public static int count(int[] coins, int N, int index) {
    if (N == 0) return 1;
    if (index == coins.length) return 0;

    int i = 0;
    int ways = 0;
    do {
      int value = coins[index] * i;
      if (value > N) break;
      ways += count(coins, N - value, index + 1);
      i++;
    } while (true);
    return ways;
  } // count
  
} // CoinChange