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++) {
sublist.add(numbers.get(i));
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 :)
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>();
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 conclusion:
[1, 3]
[4]
[4, 0]
source to share
@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 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 :)
source to share
In the code for the 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 is j
never used. So you do the same thing multiple times and I seriously doubt what you want to do.
source to share
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());
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
}
}
}
source to share