logo CodeStepByStep logo


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

Write a recursive function named largestSum that accepts a reference to a vector of integers V and an integer limit N as parameters and uses backtracking to find the largest sum that can be generated by adding elements of V that does not exceed N. For example, if you are given the vector {7, 30, 8, 22, 6, 1, 14} and the limit of 19, the largest sum that can be generated that does not exceed is 16, achieved by adding 7, 8, and 1. If the vector is empty, or if the limit is not a positive integer, or all of V's values exceed the limit, return 0. Assume that all values in the vector are non-negative.

Each index's element in the vector can be added to the sum only once, but the same number value might occur more than once in the vector, in which case each occurrence might be added to the sum. For example, if the vector is {6, 2, 1} you may use up to one 6 in the sum, but if the vector is {6, 2, 6, 1} you may use up to two sixes.

For the most part you do not need to worry about efficiency, but your code should not perform exactly the same unnecessary deep exploration multiple times. You should also avoid making copies of data structures extremely high numbers of times by always passing them by reference.

The vector passed to your function must be back to its original state at the end of the call. Either do not modify it, or if you modify it, fully undo your modifications before the function returns.

Constraints: Do not declare any global variables. You can use any data structures you like, and your code can contain loops, but the overall algorithm must be recursive and must use backtracking. You are allowed to define other "helper" functions if you like; they are subject to these same constraints.

Type your solution 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

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.