Home > Software engineering >  Why I am getting empty 2d ArrayList such as [ [ ], [ ], [ ], ... ] instead of adding ArrayList in 2d
Why I am getting empty 2d ArrayList such as [ [ ], [ ], [ ], ... ] instead of adding ArrayList in 2d

Time:07-21

I am solving Subsets Problem on leetcode using java with the help of recursion. But the problem is instead of adding ArrayList to 2d ArrayList I am getting { {}, {}, {}, ...} as my output instead of { {1,2,3}, {1,2}, {1,3}, {1}, {2,3}, {2}, {3}, {} }. Can someone explain me why this is happening?

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

public static void helper(int index, List<List<Integer>> result, List<Integer> arr, int[] nums){
    if(index == nums.length){
        result.add(arr);
        return;
    }
    arr.add(nums[index]);
    helper(index 1, result, arr, nums);
    arr.remove(arr.size()-1);
    helper(index 1, result, arr, nums);
}

Output of above code

Also, when I write this code it work correctly. Why?

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList(); // pay attention 
    List<Integer> arr = new ArrayList<Integer>();
    helper(0, result, arr, nums);
    return result;
}

public void helper(int index, List<List<Integer>> result, List<Integer> arr, int[] nums){
    if(index == nums.length){
        result.add(new ArrayList<Integer>(arr)); // pay attention 
        return;
    }
    arr.add(nums[index]);
    helper(index 1, result, arr, nums);
    arr.remove(arr.size()-1);
    helper(index 1, result, arr, nums);
}

Screenshot of correct output

CodePudding user response:

When you use result.add(arr); , all arr that added to result are the same one defined in your main function. As arr is [] at last, your result is [[], [], [], [], [], [], [], []].

But when you use result.add(new ArrayList<Integer>(arr));, you create an anonymous new ArrayList object, which has the same content as arr has at the time. But when arr's content changed, it does nothing to this anonymous object. So at last ,you got the result with different children.

  • Related