### 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;`
`}`