leetcode: Subsets II

问题描述：

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

原问题链接：https://leetcode.com/problems/subsets-ii/

 

问题分析

　　这个问题有一个比较简单的思路，就是基于前面subsets问题的基础，在每次往列表里加入元素的时候判断一下是否有现存的元素来去除重复。这种方式的代码实现如下：

 

public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] num) {
        Arrays.sort(num);
        List<List<Integer>> lists = new ArrayList<List<Integer>>();
        for(int i = 0; i < 1 << num.length; i++) {
            List<Integer> list = new ArrayList<Integer>();
            for(int j = 0; j < num.length; j++) {
                if((i & (1 << j)) > 0)
                    list.add(num[j]);
            }
            if(!lists.contains(list))
                lists.add(list);
        }
        return lists;
    }
}

　　这种方式是基于求所有子集方法的代码加了个重复检查的部分。但是在出现重复元素比较多的情况下会不断的要去list里查找比较，所以性能会相对比较低。

　　除了上述的办法，其实我们还有一种思路。就是对于一个数组来说，它可以有一种递推的情况。最开始当这个数组有0个元素的时候，它所有的取值就是0个，也就是说我们返回一个空的数组作为它的子集。

　　而如果这时候有１个元素了呢，那么它就是在原来的基础上增加一个包含有这个元素本身的子集。在这里我们就有了两个集合元素：[[], [1]] 。也就是空集和这个元素本身。如果对这个过程做更加一般化的推导的话，就会发现对于第i个元素来说，它前面的i - 1个元素构成的集合我们已经得到了。相当于已经有了前面i - 1个元素构成的所有子集，那么这个子集对于第i个元素来说相当于是不选择第i个的所有情况。那么对于加入第i个元素的情况来说，就需要将这个元素依次增加到原来的每个元素里作为新的选择情况。

　　这样，我们就得到了一个一般情况下生成集合子集的一个思路。就是首先取空集放到一个列表里。然后每次取一个元素和这个列表里的元素合并，新生成的结果也加入到列表里。这样列表不断累加，生成了所有的情况。但是在这个问题里，我们还有重复的元素，该怎么来处理呢？

　　在这里我们需要稍微用一个技巧，首先将这些数组元素排序。这样相同的元素就肯定都挨在一起了。每次取一个位置的元素时就和它前面的元素去比较，如果这个元素和前面的元素不同，说明是一个新的元素，按照前面的思路，需要从头开始去和每个元素合并生成新结果。否则说明它的前一个元素已经和之前的那些元素生成了一遍结果集，它就不应该再去重新生成一遍了，而是应该从它前一个元素和之前所有结果开始归并的地方继续进行合并。要实现这一点，需要用一个变量来记录每次前一个元素合并完之后所在的位置。然后在下一个循环开头的时候判断一下，如果nums[i]  != nums[i - 1]，则将开始的部分begin = 0，否则就保持begin = 上次合并完所在的位置。

　　详细的代码实现如下：

 

public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>());
        int begin = 0;
        for(int i = 0; i < nums.length; i++){
            if(i == 0 || nums[i] != nums[i - 1]) begin = 0;
            int size = result.size();
            for(int j = begin; j < size; j++){
                List<Integer> cur = new ArrayList<>(result.get(j));
                cur.add(nums[i]);
                result.add(cur);
            }
            begin = size;
        }
        return result;
    }
}

　　这种方法因为减少了对重复元素的检查和数组扫描，它的效率会相对高一些。不过由于子集的生成本身在时间复杂度上是指数级别的。它的时间复杂度依然是O(2 ** n) 。