I cant figure out some part in my code, queue and java

Question

import java.util.*;

class Subsets {

 public static List<List<Integer>> findSubsets(int[] nums){
 List<List<Integer>> result = new ArrayList<>();

 Queue<List<Integer>> queue = new LinkedList<>();
 queue.add(new ArrayList<>()); // add empty set to queue
 result.add(new ArrayList<>()); //add empty set to result

 for(int i=0; i<nums.length; i++){

     while(!queue.isEmpty()){
        System.out.println("current result = " + result);

        List<Integer> temp = queue.poll();
        System.out.println("current temp = " + temp);

        System.out.println("before change temp, current result = " + result);

        temp.add(nums[i]);
        System.out.println(i + " add index i value to temp, i= " + temp);
        System.out.println("not yet add to result, current result = " + result);

        result.add(temp);
        System.out.println("after add temp to result, result = " + result);
      }

      //add all elements in result to queue
      int j=0;
      while(j < result.size()){
      queue.add(result.get(j));
      j++;
     }
  }
  return result;
}


 public static void main(String[] args) {
   List<List<Integer>> result = Subsets.findSubsets(new int[] { 1, 3 });
   System.out.println("Here is the list of subsets: " + result);
 }
}

and here is output of the code

current result = [[]]
current temp = []
before change temp, current result = [[]]
0 add index i value to temp, i= [1]
not yet add to result, current result = [[]]
after add temp to result, result = [[], [1]]


current result = [[], [1]]
current temp = []
before change temp, current result = [[], [1]]
1 add index i value to temp, i= [3]
not yet add to result, current result = [[3], [1]]
after add temp to result, result = [[3], [1], [3]]


current result = [[3], [1], [3]]
current temp = [1]
before change temp, current result = [[3], [1], [3]]
1 add index i value to temp, i= [1, 3]
not yet add to result, current result = [[3], [1, 3], [3]]
after add temp to result, result = [[3], [1, 3], [3], [1, 3]]
Here is the list of subsets: [[3], [1, 3], [3], [1, 3]]

I know this is kind of dirty code, but rather than just think better way, I need to understand some part I still can't figure it out.

This is code to get subsets of the given set. For example, when we are given {1,3} then output should be {}, {1}, {3}, {1,3}

I try to solve this question to use queue, but my point is that you can see second paragraph of the result output

before change temp, current result = [[], [1]]
1 add index i value to temp, i= [3]
not yet add to result, current result = [[3], [1]]

You definitely can see the point when you look at my code, I do nothing on result, I just add new value to temp, but result suddenly changed.

I am not able to figure out what I did wrong or I may have wrong basis on queue?

Answer 1

To fix the error you have, you must understand that you are adding the same list reference to the results and the queue multiple times and thus modifying those same lists over and over again.

Changing queue.add(result.get(j)); to queue.add(new ArrayList<>(result.get(j)));, makes a new list that is a copy of the results list passed to it (not a reference to the same list like before). Because it is now copied, modifications later on like temp.add(nums[i]); no longer modify the result's lists.

import java.util.*;

class Subsets {

 public static List<List<Integer>> findSubsets(int[] nums){
 List<List<Integer>> result = new ArrayList<>();

 Queue<List<Integer>> queue = new LinkedList<>();
 queue.add(new ArrayList<>()); // add empty set to queue
 result.add(new ArrayList<>()); //add empty set to result

 for(int i=0; i<nums.length; i++){

     while(!queue.isEmpty()){
        System.out.println("current result = " + result);

        List<Integer> temp = queue.poll();
        System.out.println("current temp = " + temp);

        System.out.println("before change temp, current result = " + result);

        temp.add(nums[i]);
        System.out.println(i + " add index i value to temp, i= " + temp);
        System.out.println("not yet add to result, current result = " + result);

        result.add(temp);
        System.out.println("after add temp to result, result = " + result);
      }

      //add copy of all elements in result to queue
      int j=0;
      while(j < result.size()){
      queue.add(new ArrayList<>(result.get(j)));
      j++;
     }
  }
  return result;
}


 public static void main(String[] args) {
   List<List<Integer>> result = Subsets.findSubsets(new int[] { 1, 3 });
   System.out.println("Here is the list of subsets: " + result);
 }
}