package algorithms.Recursion;

public class RecursionMain {
	public static void main(String[] args){
		NumWaysMakeChange.waysMakeChangeDifferent(100);
	}
}

package algorithms.Recursion;

import java.util.ArrayList;

public class NumWaysMakeChange {
	static int[] coinDenoms;
	public static void waysMakeChangeDifferent(int centsToChange){
		//Prepare data
		coinDenoms = new int[]{25,10,5,1};
		int startSum = 0;
		int startDenom = 0;
		int[] startCoins = new int[coinDenoms.length];
		ArrayList<int[]> cc = waysMakeChangeDifferentRecurse(centsToChange, startSum, startDenom, startCoins);

		//Print result
		System.out.println("There are "+
		cc.size()+
		" different solutions." );

		for (int[] c: cc){
			for (int coin:c){
				System.out.print(coin+" ");
			}
			System.out.println();
		}
	}
	private static ArrayList<int[]> waysMakeChangeDifferentRecurse(int centsToChange, int currentSum, int denomIndex, int[] currentCoins){
		ArrayList<int[]> ret = new ArrayList<int[]>();
		for (int i = denomIndex; i<coinDenoms.length;i++){
			//Iterate through coins of current size or smaller
			int newSum = currentSum+coinDenoms[i];
			if (newSum>centsToChange){
				//If we pass the amount
				continue;
			}
			if (newSum==centsToChange){
				//If we hit the right amount
				currentCoins[i]++;
				ret.add(currentCoins);
				return ret;
			}
			//If we're still approaching the right amount
			int[] tempCoins = currentCoins.clone();
			tempCoins[i]++;
			//Keep going deeper
			ArrayList<int[]> differentWays = waysMakeChangeDifferentRecurse(centsToChange, newSum, i, tempCoins);
			ret.addAll(differentWays);
		}
		return ret;
	}
}