A program in Java to return the list of subsets of a given array using backtracking and recursion without using loops

Question

I wrote a program for returning a list containing lists of subsets of a given array using backtracking and recursion , I named this function subset of void return type:

import java.util.ArrayList;
public class Main{
public static void main(String[] args) {
        ArrayList<Integer> nums = new ArrayList<>();
        List<List<Integer>> list= new ArrayList<>();
        int[] arr = {2,3,5};
        subset(list,nums,arr,0);  //
        System.out.println(list);
    } 
static void subset(List<List<Integer>> list,
                   ArrayList<Integer> nums,
                   int[] arr, int index){
        if(index==arr.length){
            list.add(nums);
            return  ;
        }
        int c = arr[index];
        nums.add(c);
        subset(list,nums,arr,index+1);   //
        nums.remove(nums.size()-1);
        subset(list,nums,arr, index+1);  //
        return ;
    }
}

Expectations:

output={[],[],[],[],[],[],[],[]}
expected={[2,3,5],[2,3],[2,5],[2],[3,5],[3],[5],[]}

Why is it giving empty lists?

Answer 1

All the items of list refer to the same list nums, which is eventually cleared out, so that is what you see.

nums is not added by value, but as a reference to a memory-resident object, the same object, which is thus included several times in the resulting list-of-lists.

To remedy this you need to create a fresh copy of nums each time you want to add it to list, thus storing different objects in it.

import java.util.List;
import java.util.ArrayList;

public class Main {

    public static void main(String[] args) {

        List<Integer> nums = new ArrayList<>();
        List<List<Integer>> list = new ArrayList<>();
        int[] arr = { 2, 3, 5 };
        subset(list, nums, arr, 0);  //
        System.out.println(list);
    }

    static void subset(List<List<Integer>> list,
                       List<Integer> nums,
                       int[] arr, int index) {

        if (index == arr.length) {
            list.add(new ArrayList<>(nums));
            return;
        }
            
        int c = arr[index];
        nums.add(c);
        subset(list, nums, arr, index + 1); //
        nums.remove(nums.size() - 1);
        subset(list, nums, arr, index + 1); //                       
    }
}