java - 为什么我们要在一些递归算法中复制一个ArrayList？

Question

http://oj.leetcode.com/problems/subsets-ii/

给定一个可能包含重复项的整数集合 S，返回所有可能的子集。

注意:

* Elements in a subset must be in non-descending order.
* The solution set must not contain duplicate subsets.

例如， 如果 S = [1,2,2]，一个解决方案是:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

答案是:

public class Solution {
   public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
       ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
       ArrayList<Integer> tmp = new ArrayList<Integer>();
       Arrays.sort(num);
       sub(num, 0, tmp, ans);
       return ans;        
   }

   public void sub(int[] num, int k, ArrayList<Integer> tmp, ArrayList<ArrayList<Integer>> ans) {
       ArrayList<Integer> arr = new ArrayList<Integer>(tmp);            
       ans.add(arr);       

       for (int i = k; i < num.length; i++) {
           if (i != k && num[i] == num[i-1]) continue;

           tmp.add(num[i]);
           sub(num, i+1, tmp, ans);
           tmp.remove(tmp.size()-1);
       }
   }
}

不知道为什么

 ArrayList<Integer> arr = new ArrayList<Integer>(tmp);            
 ans.add(arr);

但不是直接的:

 ans.add(tmp);

Answer 1

如果你只是想打印出结果，因为你删除了递归调用后添加的任何元素，tmp 在函数的开始和结束处看起来应该完全相同，所以它应该没有任何区别(您的方式将是首选，因为它不会在每一步复制 ArrayList)。

但是当您将结果添加到 ans 时，问题就来了。

如果您使用自己的方式，将只有一个 ArrayList float - 您只需多次将它添加到 ans。

请注意，将它添加到 ans 中实际上并没有创建它的副本，它只是将对 ArrayList 的引用添加到 ans .因此，在添加原始元素后对其进行更改也会更改 ans 的元素。

Live demo showing the correct result by printing them out and the incorrect results in the returned array .