makeChange.java

import java.util.Arrays;
 
public class MakeChange
{
	// Returns the count of all possible ways to make exact change for the
	// given total using the coin denominations in the coins[] array.
	//
	// Each coin can be used more than once, but the order of the coins is
	// irrelevant (in other words, "1, 1, 2" and "1, 2, 1" count as a 
	// single possibility.)
	public static int changePossibilities(int total, int[] coins)
	{
		int solutions = 0;
		
		// This solution is recursive, we handle the base-case here:
		// if the total amount of change is zero, there is just one possible
		// way to resolve it, the empty set!
		if (total == 0)
		{
			return 1;
		}
		
		for (int i = 0; i < coins.length; i++)
		{
			int currentCoin = coins[i];
			
			if (currentCoin > total)
			{
				continue;
			}
			
			// Here is where we make the recursive call, we take our
			// current coin and subtract it from the total, and then
			// find the number of solutions for whatever is left.
			//
			// For example, if the call was (10, [5, 3, 1]), the
			// first time through this loop, the recursive call will
			// be (5, [5, 3, 1]).
			//
			// Using a subset of the array in subsequent interations of
			// loop is a bit subtle, but it's how we avoid counting
			// duplicate solutions. Using our example above, after the
			// recursive call to (5, [5, 3, 1]) we've counted every single
			// solution that uses the five cent coin. The only solutions
			// left are those that exclusively use some combination of three
			// and one cent coins. So, the second time through the loop, the
			// recursive call is (7, [3, 1]), and the last time through the
			// loop the recursive call is (9, [1]).
			solutions += changePossibilities(total - currentCoin,
					Arrays.copyOfRange(coins, i, coins.length));
		}
		
		return solutions;
	}
	
    public static void main(String[] args)
	{
		int coins[] = {1,3,8,17};
        System.out.println("Result: " +
				MakeChange.changePossibilities(1000, coins));
    }
}