logo CodeStepByStep logo


Language/Type: C++ recursion backtracking
Related Links:
Author: Marty Stepp (on 2016/06/16)

You have an amount of change you need to make, and an unlimited amount of coins of various denominations. Write a recursive function named makeChange that accepts two parameters: an integer representing an amount of change, and a vector of integers representing the coins' values in cents, and calculates and prints every way of making that amount of change, using the coin values in the vector. Each way of making change should be printed as the number of each coin used in the coins vector. For example, if you need to make 15 cents using pennies, nickels, and dimes, you should print these vectors:

{15, 0, 0}
{10, 1, 0}
{5, 2, 0}
{5, 0, 1}
{0, 3, 0}
{0, 1, 1}

Note that this result is by calling it with a coins vector of {1, 5, 10} representing pennies, nickels, and dimes. In this example, there were three "choices": first, we chose the number of pennies, then the number of nickels, and finally the number of dimes.

You may assume that the amount of change passed to your function is non-negative, but it could exceed 100.

Type your C++ solution code here:

This is a function problem. Write a C++ function as described. Do not write a complete program; just the function(s) above.

You must log in before you can solve this problem.

Log In

Need help?

If you do not understand how to solve a problem or why your solution doesn't work, please contact your TA or instructor.
If something seems wrong with the site (errors, slow performance, incorrect problems/tests, etc.), please

Is there a problem? Contact a site administrator.

© Marty Stepp, all rights reserved.