makeChange.clj

(defun allpossibilities (total coins)
  "Given a total amount of money, and a list of denominations, return the total number of possible combinations of denominations that would sum up to total"
  (let ((ans-table (make-hash-table :test 'equal)))
    (labels ((iter (left ans)
               (cond ((= left 0) (setf (gethash (sort (copy-list ans) #'>) ans-table) 1))
                     ((< left 0) nil)
                     (t (dolist (coin coins)
                          (iter (- left coin)
                                (cons coin ans)))))))
      (iter total nil))
    ans-table))

makeChange.coffee

COINS = [2,5,3,6].sort()
CHANGE = 10
SOLUTIONS = {}

PERSISTENCE_IS_KEY_TO_SUCCESS_ALONG_WITH_MANY_OTHER_REQUIREMENTS_OFTEN_OVERLOOKED = true


class Node
  constructor: (@parent, @value) ->
    @sum = null
    @buildPointer = 0
    @children = []
    @calculate()

  calculate: () ->
    if @parent
      @sum = @parent.sum + @value
    else
      @sum = @value
    @sum

  getPath: () ->
    path = [@value]
    node = @
    while( node.parent )
      node = node.parent
      path.unshift node.value
    path.sort().join(',')

  isSaturated: () ->
    # console.log "isSaturated", @buildPointer, COINS.length - 1
    @buildPointer >= COINS.length

  makeNextNode: () ->
    node = new Node(@, COINS[@buildPointer])
    @children.push node
    @buildPointer++
    node


solveTree = (seed) ->
  node = new Node(null,seed)
  while( PERSISTENCE_IS_KEY_TO_SUCCESS_ALONG_WITH_MANY_OTHER_REQUIREMENTS_OFTEN_OVERLOOKED )
    # console.log "#{steps}\t#{node.sum}\t#{node?.parent?.value}"
    if node.sum == CHANGE
      SOLUTIONS[ node.getPath() ] = true
      if node.parent
        node = node.parent
      else
        break

    if node.sum > CHANGE
      if node.parent
        node = node.parent
      else
        break

    if node.sum < CHANGE
      unless node.isSaturated()
        node = node.makeNextNode()
      else
        if node.parent
          node = node.parent
        else
          break

for x in COINS
  solveTree x

console.log SOLUTIONS
console.log "=",Object.keys(SOLUTIONS).length

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)
			{
				break;
			}
			
			// 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));
    }
}