logo CodeStepByStep logo


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

Write a recursive function named partitionable that accepts a reference to vector of integers as a parameter and uses recursive backtracking to discover whether the vector can be partitioned into two sub-lists of equal sum. Your function should return true if the given list can be partitioned equally, and false if not. The table below indicates various possible contents for a vector, and the value that would be returned by the call of your function:

Vector Contents Value Returned
{} true
{42} false
{1, 2, 3} true
{1, 2, 3, 4, 6} true
{2, 1, 8, 3} false
{8, 8} true
{-3, 14, 3, 8} true
{-4, 5, 7, 2, 9} false

For example, the vector {1, 2, 3} can be split into {1, 2} and {3}, both of which have a sum of 3. The vector {1, 2, 3, 4, 6} can be split into {1, 3, 4} and {2, 6}, both of which have a sum of 8. For the vector {2, 1, 8, 3}, there is no way to split the vector into two sub-vectors whose sum is equal.

You are allowed to modify the vector passed in as the parameter as you compute the answer, as long as you restore it to its original form by the time the overall call is finished. Do not use any loops in solving this problem. Your code should use recursive backtracking.

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.