Interview.java

public class Solution {

    public static int makeChangesRecursive(int amount, int[] coins) {
        if (coins.length == 0) {
            return 0;
        }

        if (amount == 0) {
            return 1;
        } else if (amount < 0) {
            return 0;
        }

        int[] removedFirstCoin = new int[coins.length - 1];
        System.arraycopy(coins, 1, removedFirstCoin, 0, coins.length - 1);

        return makeChangesRecursive(amount, removedFirstCoin) + makeChangesRecursive(amount - coins[0], coins);
    }

    public static int makeChangesIterative(int amount, int[] coins) {
        if (amount < 0) {
            return 0;
        }
        if (coins.length == 0) {
            return 0;
        }

        int tableLength = amount + 1;
        int[] table = new int[tableLength];

        // Initialize a table
        table[0] = 1;
        for (int i = 1; i < tableLength; i++) {
            table[i] = 0;
        }

        // Construct a table
        for (int coin : coins) {
            for (int i = 0; i < tableLength - coin; i++) {
                table[i + coin] += table[i];
            }
        }

        return table[amount];
    }

    public static void main(String[] args) {
        // Answer
        int[] coins = new int[] { 50, 25, 10, 5, 1 };
        System.out.println(makeChangesRecursive(100, coins));
        System.out.println(makeChangesIterative(100, coins));
    }
}