Add all subsequences of an array in an ArrayList

I am trying to add all subsequences of an array in an ArrayList. Below is my program where i am using recursion:

public class Subsequences {

    public static void main(String[] args) {
        int arr[] = {1,2,3};
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        printSubsequences(0,arr,list,result);
        System.out.println(result);
    }

    private static List<List<Integer>> printSubsequences(int i, int[] arr, List<Integer> list, List<List<Integer>> result) {
        if(i>=arr.length){
            result.add(list);
            return result;
        }
        list.add(arr[i]); //take
        printSubsequences(i 1,arr,list,result);
        list.remove(list.size()-1); //not take
        printSubsequences(i 1,arr,list,result);
        return result;
    }

}

The output of the following program is:

[[], [], [], [], [], [], [], []]

Why is my arraylist empty here? Can someone please explain?

CodePudding user response：

You are modifing the same one inner list over and over again instead of adding new lists. Change

printSubsequences(i 1,arr,list,result);

printSubsequences(i 1,arr,new ArrayList<>(list),result);

to create a new list and copy the current elements to a new sublist

private static List<List<Integer>> printSubsequences(int i, int[] arr, List<Integer> list, List<List<Integer>> result) {
    if(i>=arr.length){
        result.add(list);
        return result;
    }
    list.add(arr[i]); //take
    printSubsequences(i 1,arr,new ArrayList<>(list),result);
    list.remove(list.size()-1); //not take
    printSubsequences(i 1,arr,new ArrayList<>(list),result);
    return result;
}

When you just use a println statement, you are just printing the current state of your list for the current recursive step. You are adding and removing elements to and from the same list. Your list of lists contains 8 times the same list, so modifing one of them will reflect the change to each of them. To give you a simple example:

List<List<String>> result = new ArrayList<>();
List<String>    sagarList = new ArrayList<>();
sagarList.add("Sagar");
sagarList.add("Balyan");

System.out.println("sagarList: "   sagarList);

//now let's add the same list multiple times to the result list
result.add(sagarList);
result.add(sagarList);
result.add(sagarList);
result.add(sagarList);

System.out.println("result before removing one element from sagarList: " );
System.out.println(result);

//lets make one change to the list
sagarList.remove(sagarList.size()-1);

System.out.println("result after removing one element from sagarList: ");

System.out.println(result);

output:

sagarList: [Sagar, Balyan]
result before removing one element from sagarList: 
[[Sagar, Balyan], [Sagar, Balyan], [Sagar, Balyan], [Sagar, Balyan]]
result after removing one element from sagarList: 
[[Sagar], [Sagar], [Sagar], [Sagar]]

If you look at your result list at the last step of your recursion the list is empty, that describes why all of your sublists were empty befor making the change:

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

CodePudding user response：

because " list.remove(list.size()-1); " will clear the list finally ,and the eight lists in the result are the same list