Recursive function fails in Java (ArrayList)

user_15591292 0
Viewed 43
 static List<List<Integer>> finalSubset = new ArrayList<>();

 public static void main(String[] args) {
                ArrayList<Integer> a = new ArrayList<>();
                Integer[] array = {1, 2 ,3};
                Collections.addAll(a, array);
                subsets(a, 0);
                System.out.println(finalSubset);
    
            }
static void subsets (ArrayList<Integer> arr, int pos) {
        if (arr.size() == 0) return;
        finalSubset.add(arr); //problem
        for (int i = pos; i < arr.size(); i++) {
            Integer temp = arr.get(i);
            arr.remove (i);
            subsets(arr, i);
            arr.add(i, temp);
        }
    }

I've tried out to make a code that prints out all possible subsets of given array using ArrayList and when I run it output is correct, but when I substitute System.out.println(arr) by funalSubset.add(arr) the output is:

[[1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3]]

when it needs to be:

[1, 2, 3], [2, 3], [3], [2], [1, 3], [1], [1, 2], []

what's the reason of such output?

subset arraylist algorithm java performance
1 Answers

You are adding the same array list to finalSubset many times. You should create a copy every time you recurse, either when you add to finalSubset:

finalSubset.add(new ArrayList<>(arr));

OR when you do the recursive call:

subsets(new ArrayList<>(arr), i);

This way you have different lists that can have different things inside. If you only have one list, you just get the same thing repeated 8 times.

Also, you should add to finalSubset before you return, otherwise the empty list won't be added to finalSubset.

finalSubset.add(new ArrayList<>(arr));
if (arr.size() == 0) return;
user_51335850
Related