Ways of making change

How many ways can one make change for a given amount (say, $1.00) using an unlimited amount of quarters, dimes, nickels and pennies?
/*
 * MakeChange.cpp
 *
 *  Created on: May 14, 2012
 *      Author: Kiran Hegde
 */

#include <iostream>
#include <sstream>
#include <string>
#include <vector>

using namespace std;

/**
 * To hold quantity of each denomination through recursive calls
 */
struct Change {
    int quarters; //25c
    int dimes; //10c
    int nickels; //5c
    int pennies; //1c
};

/**
 * Recursively call this function with the lower denominations and reduced
 * total amount.  Total amount is reduced by (# of coins * prev denom)
 */
int makeChange(int total, int denom, Change &temp, vector<Change> &output) {
    int next_denom = 0;
    switch(denom) {
    case 25:
        next_denom = 10;
        break;
    case 10:
        next_denom = 5;
        break;
    case 5:
        next_denom = 1;
        break;
    case 1:
        //Base case - call returns when no more lower denominations exists
        //Each way of making change is stored in output as a copy
        temp.pennies = total;
        output.push_back(temp);
        return 1;
    }

    int noWays = 0;
    for (int i=0; i*denom <= total; i++) {
        if (denom == 25)
            temp.quarters = i;
        if (denom == 10)
            temp.dimes = i;
        if (denom == 5)
            temp.nickels = i;
        noWays += makeChange(total - i*denom, next_denom, temp, output);
    }
    return noWays;
}

/**
 *
 */
int makeChange(int total, vector<Change> &output) {
    Change temp;
    temp.dimes = 0; temp.nickels = 0; temp.pennies = 0; temp.quarters = 0;
    //Start with the highest denomination
    return makeChange(total, 25, temp, output);
}

/**
 * Convert Change object to a string
 */
string getChangeString(Change chg) {
    ostringstream result;
    result << chg.quarters << " quarters " <<  chg.dimes <<
            " dimes " <<  chg.nickels << " nickels "
            <<  chg.pennies << " pennies";
    return result.str();
}

/**
 * Test the code
 */
int main() {
    vector<Change> changeList;
    int total = 100;
    int noWays = makeChange(total, changeList);
    cout << "There are " << noWays << " ways to make change for " << total
            << " cents using quarters, dimes, nickels and pennies:" << endl;
    for (unsigned int i=0; i<changeList.size(); i++) {
        cout << getChangeString(changeList[i]) << endl;
    }
    return 0;
}
Comments