Solution to the Coin Change Problem in Java

ChangeValidator.java

package com.ncr.mobile;

import java.util.List;

public class ChangeValidator
{
	private ChangeValidator()
	{

	}

	 /**
	 * Determines if the target amount can be created given the list of available denominations.
	 * @param denominations List of available denominations. Each element could represent a differnt note 
	 * in a currency for instance. {eg, $5, $10, $20, $50}.
	 * 
	 * Note, this method assumes an infinite amount of each denomination is available. 
	 * 
	 * The solution uses dynamic programming to build an entire solution table, bottom-up. 
	 * 
	 * The value for each element in the table represents the number of different solutions that exist for that amount.
	 * 
	 * @param target The amount being tested. The method determines if this amount can be created given the list of 
	 * denominations provided.
	 * @param breakEarly The algorithm can be used to create a complete solution table or break early upon finding
	 * the first solution. Usually best to break early.
	 * @return a boolean indicating if the given amount can be created using the denomination list (true). 
	 * Otherwise returns (false)
	 */
	public static boolean isValid(List<Integer> denominations, int target, boolean breakEarly)
	{
		if (denominations.size() == 0)
			throw new IllegalArgumentException("List cannot be empty");

		if (target < 0)
			throw new IllegalArgumentException("Target cannot be negative");

		if (target == 0)
			return true;

		int results[] = new int[target + 1];
		results[0] = 1;

		for (int i = 0; i < denominations.size(); ++i)
		{
			// start with j={the first denomination value haven't tried yet}, don't loop beyond the target size
			for (int j = denominations.get(i); j <= target; ++j)
			{
				int difference = j - denominations.get(i);
				
				results[j] += results[difference];
				if (breakEarly && j == target && results[j] > 0)
					return true;
			}
		}
		
		if(results[target] == 0)
			return false;

		return true;
	}
}