Я не могу понять какую-то часть в моем коде, очереди и 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);
 }
}

и вот вывод кода

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]]

Я знаю, что это довольно грязный код, но вместо того, чтобы просто думать лучше, мне нужно понять кое-что, что я до сих пор не могупонять это.

Это код для получения подмножеств данного набора.Например, когда нам дают {1,3}, тогда выходные данные должны быть {}, {1}, {3}, {1,3}

Я пытаюсь решить этот вопрос, чтобы использовать очередь, но я хочу сказать, что вы можете видеть второй абзац вывода результата, но результат внезапно изменился.

Я не могу понять, что я сделал неправильно, или у меня неправильная база в очереди?

Answer 1

Чтобы исправить возникшую ошибку, вы должны понимать, что вы добавляете одну и ту же ссылку на список к результатам и очереди несколько раз и, таким образом, модифицируете одни и те же списки снова и снова.

Изменение queue.add(result.get(j)); на queue.add(new ArrayList<>(result.get(j))); создает новый список, который является копией переданного ему списка результатов (а не ссылкой на тот же список, что и раньше).Поскольку теперь оно скопировано, изменения, такие как temp.add(nums[i]);, больше не изменяют списки результатов.

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