CODEWITHSUNDEEP
javarecursionbacktracking
hello253
hello253

Reputation: 1459

Java recursive backtracking problem

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.

Upvotes: 1

Views: 2186

Answers (4)

user684934
user684934

Reputation:

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.

Upvotes: 4

rockerest
rockerest

Reputation: 10508

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.

Upvotes: 0

dlev
dlev

Reputation: 48596

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.

Upvotes: 1

Saurabh Gokhale
Saurabh Gokhale

Reputation: 46405

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.

Upvotes: 1

Related Questions