CODEWITHSUNDEEP
javarecursionbacktrackingsubset-sum
Loolooii
Loolooii

Reputation: 9162

List of subsets of which their elements add up to n using recursion

I'm writing this function which I want to print all the sublists of a given list with integers. The sum of these integers should be equal to a given number n. There is also a help variable i which starts with value 0. Both the list and each sublist are an ArrayList. So the method looks like this right now:

public static void printSublists(ArrayList numbers, ArrayList sublist, int n,
            int i) {

        if (sublist.sum() == n) {
            System.out.println(sublist.toString());
        } 
        else {
            for (int j = 0; j < numbers.size(); j++) {
                sublist.add(numbers.get(i));
                printSublists(numbers, sublist, n, i + 1);
                sublist.remove(numbers.get(i));
            }
        }
    }

Of course I already have the method sum(). The method does this now: Lets say numbers = [1, 3 , 4] and n == 4, then the method should print [4] and [1 ,3], but it only prints [1, 3] ? I think the for-loop has to do the trick right? I would appreciate it if someone puts me on the right track.

update: the values I'm giving to the method: 

numbers = [1, 3, 4]
n = 4
i = 0
sublist = []

UPDATE 2:

I forgot to say that I want it to be recursive :)

Upvotes: 3

Views: 3440

Answers (4)

Andrzej Jozwik
Andrzej Jozwik

Reputation: 14649

@Test
public void test() {
    printSublists(new HashSet<Integer>(Arrays.asList(2, 3, 4, 1, 2)), new HashSet<Integer>(), 4);
}

private void printSublists(Set<Integer> numbers, Set<Integer> subList, int expected) {

    for (Integer element : numbers) {
        subList.add(element);
        if (sum(subList) == expected) {
            System.out.println("result =" + subList);
        }
        Set<Integer> listWithoutElement = withoutElement(numbers, element);
        printSublists(listWithoutElement, subList, expected);
        subList.remove(element);

    }
}

private Set<Integer> withoutElement(Set<Integer> numbers, Integer element) {
    Set<Integer> newList = new HashSet<Integer>(numbers);
    newList.remove(element);
    return newList;
}

private int sum(Collection<Integer> sublist) {
    int sum = 0;
    for (Integer e : sublist) {
        sum += e;
    }
    return sum;

}

Here is your solution. This problem should be for sets, not for list.

If you have set [2,3,4,1,2] the solution should be [3,1] [4] [2,2]. Then the problem has to be recursive. You have to remove duplication of course :)

Upvotes: 2

Andreas Dolk
Andreas Dolk

Reputation: 114767

Recursion stops when you see the first sublist with a sum of n. The problem is not (only) the loop but the exit criteria. Your recursive function should stop when the sublist length is 0.

Here I just wrote a working, recursive solution for your problem. It is different but I wasn't able to fix yours. While you start with an empty sublist, I chose to init the recursion with the full list an divide it into smaller sublists. This creates a tree like structure:

                        [1234]
                     [123]  [234]
                   [12] [23]   [34]
                  [1][2]  [3]    [4]

We see immediately, that we have to walk down "right" until we reach the first leaf (1), then we only walk "left". This way we visit all sublists only once.

Here's the idea written in Java:

public static void main (String[] args) {
  ArrayList<Integer> list = new ArrayList<Integer>();
  list.add(1);
  list.add(3);
  list.add(4);
  list.add(0);
  printSublists(list, list, 4, true, 0);
}

public static void printSublists(List<Integer> numbers, List<Integer> sublist, int n, boolean walkRight, int level) {

  // the test
  if (sum(sublist) == n)
     System.out.println(sublist);

  // the exit criteia (leaf reached)
  if (sublist.size() == 1)
     return;

  // visit the right sublist
  if (walkRight) 
    printSublists(numbers, sublist.subList(0, sublist.size()-1), n, walkRight, level+1);

  // we only walk the right path once
  walkRight = false;

  // visit the left sublist
  printSublists(numbers, sublist.subList(1, sublist.size()), n, walkRight, level+1);
}

And that's the output:

[1, 3]
[4]
[4, 0]

Upvotes: 2

Kshitij
Kshitij

Reputation: 8614

probably u will need to do something this way -

public static void printSublists(ArrayList numbers, ArrayList sublist, int n,
        int i) {

    if (sublist.sum() == n) {
        System.out.println(sublist.toString());
        sublist.removeAll(sublist);//added remove all here
    } 
    else {
        //for (int j = 0; j < numbers.size(); j++) {//commented this line
        while(i<number.size()){//need while loop
            sublist.add(numbers.get(i));
            printSublists(numbers, sublist, n, ++i);//i+1 changed to ++i
            //sublist.remove(numbers.get(i));// commented here
        }
    }
}

Upvotes: 0

Don Roby
Don Roby

Reputation: 41127

In your code's for loop:

        for (int j = 0; j < numbers.size(); j++) {
            sublist.add(numbers.get(i));
            printSublists(numbers, sublist, n, i + 1);
            sublist.remove(numbers.get(i));
        }

The variable j is never used. So you're doing exactly the same thing repeatedly, which I seriously doubt is what you want to do.

Upvotes: 0

Related Questions