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);
如果您只想打印结果,由于您删除了在递归调用之后添加的任何元素tmp
,因此在函数的开始和结束处应该看起来完全相同,因此不应有任何区别(您的方式会首选,因为它不会ArrayList
在每个步骤都复制)。
但是,当您将结果添加到时,问题就来了ans
。
如果您使用自己的方式,那么只会有一个ArrayList
浮动对象-您只需将其添加ans
多次即可。
请注意,将其添加到ans
不实际创建它的副本,它只是增加了一个参考ArrayList
来ans
。因此,在添加原始文件后对其进行更改也会更改的元素ans
。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句