Here are five functions, with descriptions of what they are supposed to do. They

Question

Here are five functions, with descriptions of what they are supposed to do. They are incorrectly implemented. Replace the incorrect implementations of these functions with correct ones that use recursion in a useful way; your solution must not use the keywords while, for, or goto. You must not use global variables or variables declared with the keyword static, and you must not modify the function parameter lists. You must not use any references or pointers as parameters except for the parameters representing arrays.

Explanation / Answer

Base cases :-

1) If target = 0 then return true

2) if target is not zero but size is zero then retuen false as there are no elements

The comboSum problem can be divided into two subproblems
…a) Include the last element, MEANING SIZE = SIZE-1, TARGET = TARGET – A[SIZE-1]

…b) Exclude the last element, MEANING SIZE = SIZE-1, TARGET = TARGET

Then we will take OR that is if any subproblem result in true that means answer is possible return true;

bool comboSum(const int a[], int size, int target) {

// Base Case

   if (target == 0)

     return true;

   if (target != 0 && size == 0) {

     return false;

//Base case ends

//Cheking two subproblems and taking OR

bool answer = comboSum(a, size-1, target) || comboSum(a, size-1, target - a[size-1])

return answer;

}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.