CTCI 9.8

Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent), write code to calculate the number of ways representing n cents.

CTCI 9.8.java

public static int countWays(int cents){
    int[] way = new int[4];
    return countWays(cents, way, 0);
}

public static int countWays(int cents, int[] way, int thisBillFlag){
    if(cents < 0) return 0;
    int thisBill = 1, nextBillFlag = 1;
    switch(thisBillFlag){
        case 0: thisBill = 25; nextBillFlag = 1; break;
        case 1: thisBill = 10; nextBillFlag = 2; break;
        case 2: thisBill = 5; nextBillFlag = 3; break;
        case 3: way[3] = cents; System.out.println(Arrays.toString(way)); return 1;
    }
    int count = 0;
    for(int i = 0; i <= cents / thisBill; i++){
        way[thisBillFlag] = i;
        count += countWays(cents - i * thisBill, way, nextBillFlag);
    }
    return count;
}