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