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

I am writing this function which I want to print all sublists of a given list with integers. The sum of these integers must be equal to the specified number n

. There is also a reference variable i

that starts at 0. Both lists and each sublist are ArrayList

. So the method looks like this:

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++) {
printSublists(numbers, sublist, n, i + 1);
sublist.remove(numbers.get(i));
}
}
}

Of course, I already have a method sum()

. The method does it now: Let's 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 should be doing the trick right? I would be grateful if someone would put me on the right track.

update: the values ​​I give 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 :)

+3

source to share

The recursion stops when you see the first sum sublist n

. The problem is not (only) in the loop, but in the exit criteria. Your recursive function should stop when the length of the sublists is 0.

Here I just wrote a working, recursive solution for your problem. It's different, but I couldn't fix yours. When you start with an empty sublist, I decided to start the full list recursion by dividing it into smaller sublists. This creates a tree-like structure:

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

We immediately see that we need to go down "to the right" until we reach the first sheet ( 1

), then we will only go "to the left". Thus, we visit all sub-lists only once.

Here's an idea written in Java:

public static void main (String[] args) {
ArrayList<Integer> list = new ArrayList<Integer>();
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 conclusion:

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

+2

source

@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) {
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 list.

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

+2

source

In the code for the loop:

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

The variable is j

never used. So you do the same thing multiple times and I seriously doubt what you want to do.

0

source

You will probably 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());
}
else {
//for (int j = 0; j < numbers.size(); j++) {//commented this line
while(i<number.size()){//need while loop
printSublists(numbers, sublist, n, ++i);//i+1 changed to ++i
//sublist.remove(numbers.get(i));// commented here
}
}
}

0

source

All Articles