Java recursive backtracking problem

Question

Having some trouble with this recursive backtracking problem:

"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."

For example, the list [1, 2, 3] can be partitioned into the sublists [1, 2] and [3], so it would produce a result of "true."

My solution seems correct, but returns false no matter what. I don't understand why.

public static boolean partitionable(List<Integer> list1) {
        List<Integer> list2 = new ArrayList<Integer>();
        return partitionable(list1, list2);
    }

public static boolean partitionable(List<Integer> list1, List<Integer> list2) {
    boolean finalAnswer = false;
    int sum1 = 0;
    int sum2 = 0;
    for (int i = 0; i < list1.size(); i++) {
        sum1 += list1.get(i);
    }
    for (int i = 0; i < list2.size(); i++) {
        sum2 += list2.get(i);
    }
    if (sum1 == sum2) {
        return true;
    } else {
        for (int i = 0; i < list1.size() - 1; i++) {
            int number = list1.remove(i);
            list2.add(number);
            finalAnswer = partitionable(list1, list2);
            list2.remove(list2.size() - 1);
            list1.add(i, number);
        }
    }
    return finalAnswer;
}

EDIT: I fixed the problem of removing the element from list1 twice.

score 4 · Accepted Answer · 2011-07-25 01:45:59Z

4

You are calling list1.remove(i) twice. That will probably mess up your algorithm, because you're removing two numbers, and saving only one of them to add to list2.

If it's still not working, I've also noticed that you're neglecting the last element of list1 as a candidate to go over to list2. I don't see an algorithmic reason for this to happen: you should try removing the -1 from your for loop.

edited Jul 25, 2011 at 1:45

answered Jul 25, 2011 at 1:30

user684934

Sign up to request clarification or add additional context in comments.

Comments

Saurabh Gokhale · Accepted Answer · 2011-07-25 01:30:31Z

1

Problem is of calling list1.remove(i) twice. This won't work.

You'r removing two numbers from list1 and while saving it in list2, you are saving only 1.

answered Jul 25, 2011 at 1:30

Saurabh Gokhale

46.5k35 gold badges139 silver badges163 bronze badges

Comments

dlev · Accepted Answer · 2011-07-25 01:31:25Z

1

Your recursive case (the else block) should check to see if finalAnswer == true, and return it immediately if that's the case. Otherwise, you'll skip over it onto cases where false is returned, and eventually return that at the bottom.

That won't solve the whole problem, since you're also removing an item from list1 twice. Fixing both should get you the right solution.

answered Jul 25, 2011 at 1:31

dlev

48.7k5 gold badges127 silver badges133 bronze badges

Comments

rockerest · Accepted Answer · 2011-07-25 01:38:42Z

0

Excuse me for not answering your question directly, but my understanding of the question posed necessitates a different answer.

The original question asks this:
Your method should return true if the given list can be partitioned equally

And you later claim this:
[1, 2, 3] can be partitioned into the sublists [1, 2] and [3], so it would produce a result of "true."

This rings incorrect to me. Would the proper solution (ignoring the recursive backtracking requirement for a moment) be to count the number of integer elements, % 2 and return NOT result?

In other words:

List has three elements.  
Divide by 2, remainder 1.
Return 0, list is not equally dividable.

List has four elements.
Divide by 2, remainder 0.
Return 1, list is equally dividable.

Please let me know where I've misunderstood the question.

answered Jul 25, 2011 at 1:38

rockerest

10.5k3 gold badges39 silver badges67 bronze badges

2 Comments

hello253 Over a year ago

the sub-list are to have equal sums, not equal numbers of elements

rockerest Over a year ago

@hello253, AH, that makes a lot of sense now. Thank you.

Collectives™ on Stack Overflow

Java recursive backtracking problem

4 Answers 4

Comments

Comments

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related