logo CodeStepByStep logo


Language/Type: C++ recursion backtracking
Related Links:

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.

Function: Write a C++ function as described, not a complete program.

You must log in before you can solve this problem.

Log In

Need help?

Stuck on an exercise? Contact your TA or instructor.

If something seems wrong with our site, please

Is there a problem? Contact us.