## partitionable

Language/Type: Java recursion recursive backtracking
Author: Marty Stepp (on 2011/02/17)

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

List 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 list `[1, 2, 3]` can be split into `[1, 2]` and `[3]`, both of which have a sum of 3. The list `[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 list `[2, 1, 8, 3]`, there is no way to split the list into two sub-lists whose sum is equal.

You are allowed to modify the list 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. You may assume that the list passed in is not `null`, but it might be empty. Do not use any loops in solving this problem.

Type your solution here:

This is a method problem. Write a Java method as described. Do not write a complete program or class; just the method(s) above.

You must log in before you can solve this problem.

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.