个人记录-LeetCode 90. Subsets II

2019-11-08 01:40:48

字体：大中小

来源：转载

供稿：网友

问题：

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example, If nums = [1,2,2], a solution is:

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

代码示例：

解决这个，最后先回忆一下LeetCode 78。 LeetCode 78与LeetCode 90唯一的差别是，LeetCode的输入数组中没有重复的数据。

LeetCode 78的一种解法的思路类似于：

public class Solution { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> res = new ArrayList<>(); ArrayList<Integer> tmp = new ArrayList<>(); Arrays.sort(nums); //首先增加空集 res.add(tmp); dfs(res,tmp,nums,0); return res; } public void dfs(List<List<Integer>> res, ArrayList<Integer> tmp, int[] nums, int pos){ for(int i=pos; i<=nums.length-1;i++){ //每增加一个新的数，都构成一个新的子集 tmp.add(nums[i]); //将新的集合加入结果 res.add(new ArrayList<Integer>(tmp)); //进入下一层的迭代 //避免重复，下一个加入的数，在当前数位置的后面 dfs(res,tmp,nums,i+1); //当前数，作为本层的结尾，已经加入了所有的结果 //需要移除，将下一个数作为本层的结果 tmp.remove(tmp.size()-1); } }}

上面代码运行的结果类似于：

比如，输入集合为［1，2，3］，那么依次加入的结果类似于：[] //从空集开始，每次增加一个元素，都构成一个新的子集[1] //第1层迭代[1,2] //第2层迭代[1,2,3] //第3层迭代 //第4层迭代，pos大于length-1，无实际操作 //回到第3层，移除3 //3后面没有其它数了，回到第2层 //移除2[1,3] //第2层跌代，加入2后面的数3 //第3层迭代，pos大于length-1，无实际操作 //回到第2层，移除3 //3后面没有其它数了，回到第1层 //移除1[2] //第1层跌代，加入1后面的数2[2,3] //第2层跌代，加入3 //第3层迭代，pos大于length-1，无实际操作 //回到第2层，移除3 //3后面没有其它数了，回到第1层 //移除2[3] //第1层跌代，加入2后面的数3 //第2层迭代，pos大于length-1，无实际操作 //回到第1层，移除3 //3后面没有其它数了，结束

在LeetCode 78的基础上，LeetCode 90就比较好解决了，只要避免不必要的重复就行。代码示例如下：

public class Solution { public List<List<Integer>> subsetsWithDup(int[] nums) { List<List<Integer>> res = new ArrayList<>(); ArrayList<Integer> tmp = new ArrayList<>(); Arrays.sort(nums); res.add(tmp); dfs(res,tmp,nums,0); return res; } public void dfs(List<List<Integer>> res, ArrayList<Integer> tmp, int[] num, int pos){ for(int i=pos;i<=num.length-1;i++){ tmp.add(num[i]); res.add(new ArrayList<>(tmp)); dfs(res,tmp,num,i+1); tmp.remove(tmp.size()-1); //就是额外增加了这一部分 while(i<num.length-1 && num[i]==num[i+1]) { i++; } } }}

举例如下：

假设集合为［2，3，3］，如果按照LeetCode 78中的代码运行，结果如下：[][2] //1层[2,3] //2层[2,3,3] //3层 //4层未实际运行，回退到第3层，移除最后一个3 //3后没其它数，回到第2层 //回到第2层后，移除第2个三[2,3] //然后添加最后一个3，形成重复 //以下分析类似[3][3,3][3]

因此，每层迭代，移除的数不能和新加入的数一致。

上一篇：广播的使用

下一篇：springMVC源码分析--视图AbstractView和InternalResourceView（二）