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);
}
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);
}
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.