public class HW2CoinCHangingVariant {
    // coins: denomination; B: total exact value; k # of coins
    public boolean coinChanging(int[] coins, int B, int k) {
        if (coins == null) {
            return false;
        }
        if (B == 0) {
            return true;
        }
        boolean[][][] c = new boolean[coins.length + 1][B + 1][k + 1];
        c[0][0][0] = true;
        for (int i = 0; i < c.length; i++) {
            for (int b = 0; b < c[0].length; b++) {
                for (int j = 0; j < c[0][0].length; j++) {
                    if (b == 0) {
                        c[i][b][j] = true;
                    } else if (i == 0 || j == 0) {
                        c[i][b][j] = false;
                    } else if (b >= coins[i - 1]) {
                        c[i][b][j] = c[i - 1][b][j] || c[i - 1][b - coins[i - 1]][j - 1];
                    } else {
                        c[i][b][j] = c[i - 1][b][j];
                    }
                }
            }
        }
        return c[c.length - 1][c[0].length - 1][c[0][0].length - 1];
    }
}