logo CodeStepByStep logo

isMeasurable

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

Write a recursive function named isMeasurable that determines whether it is possible to weigh out exactly a given amount on two scales, given a target amount and a collection of weights to use. Your function accepts two parameters: a reference to a vector of integers representing weights that you can use, and an integer target weight amount.

For example, suppose that you have only two weights: a 1-ounce weight and a 3-ounce weight. With these you can easily measure out 4 ounces by placing both weights on one side of the scale, as shown:

figure

You can also measure out 2 ounces by shifting the 1-ounce weight to the other side, as follows:

figure

Suppose that the variable weights has been initialized as follows:

Vector weights;
weights += 1, 3;

Given these values, the calls of isMeasurable(weights, 4) and isMeasurable(weights, 2) would both return true. On the other hand, the call of isMeasurable(weights, 5) would return false because it is impossible to use the 1- and 3-ounce weights to add up to 5 ounces. You don't need to use every weight in the vector to reach the given target; in the example above, calls of isMeasurable(weights, 3) and isMeasurable(weights, 1) would return true because you can make those amounts by using only a single weight in each case.

If the target weight passed is 0, your function should always return true. You may assume that the value of the target weight passed will not be initially negative, and that the vector passed does not contain any negative weight values in it.

Constraints: You may use a loop in your solution if you like, but the overall algorithm must use recursion and backtracking. You may define helper functions if you like.

Type your C++ solution code 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.