Question

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.

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

2

*/
bool CoinChange (c[0...n-1], v) {

if (v==0)

for i=0 to n-1: if (c[i]==v)

//fill in the blank here

 //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

The required code followed by sample output has been given below, also the required answers for tracing and listing the recursive calls has been done in the comment lines, also for getting the list of recursive calls of any functions you can uncomment the first line in the function.

CODE:

#include<iostream>
using namespace std;

bool CoinChange (int c[],int n, int v) {                                 // when v equals 14, and c = {3,4,6,10}

    // cout<<"CoinChange[c,n,"<<v<<"] --> ";                              // for the list of function call just uncomment this line, the list will be showed in the output

    if (v==0){

        return true;
    }


    for (int i=0;i<n;i++){

        if (c[i]==v)
                                                                            // will be checked for i = 0 and c[0] = 3 != 14 so go it else condition
            return true;


        else if (c[i]<v){                                              //  3 < 14 so statements under else if body executed

             if (CoinChange (c,n,v-c[i]) == true)                        // the same function get called for (c,n,14-3) = (c,n,11) now it will be checked for the value v = 11 for same coins, again it comes here (same statement)
                return true;                                             // and then will call (c,n,11-3) = (c,n,8) and so on...


        }                                                            // so for v = 14, the trace of function execution will be, (lets call the function CC)
                                                                    // CC(c,n,14) --> CC(c,n,11) --> CC(c,n,8) --> CC(c,n,5) --> CC(c,n,2) --> CC(c,n,1) --> CC(c,n,4)
                                                                    //  CC(c,n,1) --> True

    }
    return false;                                                      // backtracking can happens when the first time CC[c,n,2] get called because there is no element less or equal to 2 so it returns false so the program backtrack from here
}

/* The order of recursive calls will be

    CC[c,n,14] --> True
    CC[c,n,11] --> True ( when i = 0 for v = 14)
    CC[c,n,8] --> True  (when i = 0 for v = 11)
    CC[c,n,5] --> False (when i = 0 for v= 8)
    CC[c,n,2] --> False ( when i = 0 for v = 5)
    CC[c,n,1] --> False (when i = 1 for v = 5)   ( backtracking)
    CC[c,n,4] --> True (when i = 1 for v = 8)
    CC[c,n,1] --> False ( when i = 0 for v = 4) and i gets increased for v = 4, so i becomes 1 and c[1] = 4 and v = 4 so it returns true.

*/



int main(){

    int c[] = {2,4,6,10};
    int n = 4;
    int v = 34;
    cout<<"\nFor v = 34 and c = {2,4,6,10}"<<endl;
    if (CoinChange(c,n,v))
        cout<<"True"<<endl;
    else
        cout<<"False"<<endl;

    v = 17;
    cout<<"\nFor v = 17 and c = {2,4,6,10}"<<endl;
    if (CoinChange(c,n,v))
        cout<<"True"<<endl;
    else
        cout<<"False"<<endl;

    c[0] = 3;
    v = 14;
    cout<<"\nFor v = 14 and c = {3,4,6,10}"<<endl;
    if (CoinChange(c,n,v))
        cout<<"True"<<endl;
    else
        cout<<"False"<<endl;



    return 0;


}

OUTPUT:

NOTE: In case of any query, you are always welcomed in the comment section. HAPPY LEARNING!!