java - 我无法弄清楚我的代码、队列和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]]

我知道这是一种肮脏的代码， 但我需要理解一些我仍然无法弄清楚的部分，而不仅仅是想出更好的方法。

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}

我尝试使用队列来解决这个问题， 但我的观点是你可以看到结果输出的第二段

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

当你看我的代码时，你肯定能明白这一点， 我对结果没有做任何事情，我只是向临时添加新值，但结果突然改变了。

我无法弄清楚我做错了什么，或者我的队列基础可能有误？

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