Question

Coin Change Problem) Given a list of positive integers c[0...n − 1], and a positive integer v, decides
whether we can use numbers from c[0...n − 1] to make a sum of v, allowing any particular number
in the list to be used multiple times. Or, mathematically, this means that there exists non-negative
integer coefficients, x0, x1, ..., xn−1, such that v = x0c[0] + x1c[1] + ...xn−1c[n − 1].
For example, given c[0...3] = {2, 4, 6, 10}, and v = 17, the function shall return false, as it’s impossible
to use numbers from c to add up to 17.
Given c[0...3] = {2, 4, 6, 10}, and v = 34, the function shall return true, as 34 can be expressed as 17
2’s added up (there are other ways to make value 34 as well).
Based upon the pseudocode given at the end,
(a) implement and test the following C++ function (minimally, you shall test the function with
examples given above.
/* Return true if v can be expressed as sums of values from coins (repetition is allowed)
@param coins is a vector of positive int values
@param v is a positive int
@return true if v can be written as a sum of values from coins, return false otherwise
*/
bool CoinChange (vector<int> coins, int v)
(b) In comment of your code, provide a tracing of the function’s execution with input: coins[0...3] =
{3, 4, 6, 10}, and v = 14. You should:
• list in order the recursive calls made, with the parameters passed and values returned for each
call.
• Comment on when backtracking happens.
(c) (Extra credit): how to make the function prints out the numbers that are used to make the
change?
Pseudocode
/*
Return true if v can be expressed as sum of values from c[0...n-1]
@param c[0...n-1]: stores n positive integers
@param v: non-negative integers
*/
bool CoinChange (c[0...n-1], v)
{
if (v==0)
//fill in the blank here
for i=0 to n-1:
2
if (c[i]==v)
//fill in the blank here
else if (c[i]<v)
//Think: if we include c[i] to make change amount of
// v, then we only need to make change amount of _____
if (CoinChange (c, ) == True): //fill in the parameter for the
return true; //function call above
// If we haven’t returned true by now, return false
return false;
}

Answer 1

C++ Implementation of the required pseudocode.

#include<bits/stdc++.h>
using namespace std;
bool CoinChange(vector<int> coins,int v)
{
    int i;
    if(v == 0)          // When amount of 0 is to be made return TRUE as it can be made by discarding all coins.
        return true;
    for(i=0;i<coins.size();i++) // For each coin in the vector check the inside conditions
    {
        if(coins[i] == v)       // If amount to be made is equal to coins[i] then just by selecting this coin
            return true;        // required change is made so return TRUE.
        else if(coins[i] < v)
        {                                       // If coins[i] is less than the amount select the coins[i] and then
            if(CoinChange(coins,v - coins[i]))  // check if rest amount i.e. v - coins[i] is possible or not.
                return true;
        }
    }
    return false;               // If by all denominations value the given amount is not formed then return FALSE.
}
int main()
{
    vector<int> coins = {3,4,6,10}; // Test vector
    cout<<CoinChange(coins,14);     // Test function call
    return 0;
}

A recursive call tree for the given example is drawn here.

We can add an auxiliary vector in the function parameter and store the coin denomination that we are accepting at each step and finally print the auxiliary vector if function return true.