ChangeMaking

    public static int[] makeChange(int amount, int[] denominations) {
        calls = 0;

        int L = denominations.length;
        int[] counts = new int[L + 1];

        recMakeChange(amount, denominations, counts);

        //for(int d: counts) System.out.println(d);

        int[] solution = new int[counts[L]]; // length is number of tokens
        int i = 0;
        // For each index of counts referring to a denomination
        for(int j = 0; j < counts.length-1; j++) {
            // Loop x times where x is the # of that denomination needed
            for (int x = 0; x < counts[j]; x++) {
                solution[i] = denominations[j];
                // Put the needed denom in the solutions array x times
                i++;
            }
        }

        System.out.println("Finding change for: " + amount);
        System.out.println("Sum of solutions array: " + sumArr(solution));
        System.out.println("Required " + calls + " calls.");

        return solution;
    }


    public static boolean recMakeChange(int amount, int[] denom, int[] counts) {
        calls++;

        if (amount == 0)  return true;
        if (amount < 0) return false;
        if (table[amount] != null) {
            for (int k = 0; k < table[amount].length; k++)
                counts[k] = table[amount][k];
            return true;
        }

        boolean ret = false;
        int[] temp = new int[counts.length];
        int[] best = new int[counts.length];
        best[best.length-1] = amount + 1;

        for (int i = 0; i < denom.length; i++) {

            if (recMakeChange(amount - denom[i], denom, temp)) {
                if (temp[temp.length-1] < best[best.length-1]) {
                    temp[i]++;
                    temp[temp.length-1]++;
                    for(int z = 0; z<best.length;z++)
                        best[z] = temp[z];
                }
                ret = true;
            }
        }

        // Copy best into counts if solution is found...
        if (ret) {
            for(int n = 0; n < best.length; n++) counts[n] = best[n];
            table[amount] = new int[counts.length];
            for(int z = 0; z < best.length; z++)
                table[amount][z] = counts[z] = best[z];
        }

        return ret;

    }