Subsets II

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

Note:
Elements in a subset must be in non-descending order.
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],
  []
]

这道题目是Subsets 的变形，数组中包含了重复的元素，之前介绍了两种方法，这里我们可以用同样的方法解决，只要多一个判断结果是否重复就可以了。代码如下：
1，位运算方法

public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<Integer> list;
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(nums == null || nums.length == 0)
            return result;
        java.util.Arrays.sort(nums);
        for(int i = 0; i < Math.pow(2, nums.length); i++) {
            list = new ArrayList<Integer>();
            for(int j = 0; j < nums.length; j++) {
                if((i >> j & 1) == 1)
                    list.add(nums[j]);
            }
            if(!result.contains(list))
                result.add(list);
        }
        return result;  
    }
}

2，回溯法

public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        LinkedList<Integer> list = new LinkedList<Integer>();
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(nums == null || nums.length == 0) 
            return result;
        java.util.Arrays.sort(nums);
        for(int i = 0; i <= nums.length; i++) {
            getSubset(0, i, nums, list, result);
        }
        return result;
    }
    public void getSubset(int start, int lth, int[] nums, LinkedList<Integer> list, List<List<Integer>> result) {
        if(list.size() == lth) {
            if(!result.contains(list))
                result.add(new LinkedList<Integer>(list));
            return;
        }
        for(int i = start; i < nums.length; i++) {
            list.add(nums[i]);
            getSubset(i + 1, lth, nums, list, result);
            list.removeLast();
        }
    }
}

上面的代码都可以通过测试，但是我们还可以将我们的代码优化，在回溯的时候，如果后面的元素和前面的元素相同，我们就可以跳过这个元素，这样就大大提高了效率。代码如下：

public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        LinkedList<Integer> list = new LinkedList<Integer>();
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(nums == null || nums.length == 0) 
            return result;
        java.util.Arrays.sort(nums);
        getSubset(0, nums, list, result);
        return result;
    }
    public void getSubset(int index, int[] nums, LinkedList<Integer> list, List<List<Integer>> result) {
        if(index <= nums.length) {
            result.add(new LinkedList<Integer>(list));
        }
        for(int i = index; i < nums.length; i++) {
            if(i != index && nums[i] == nums[i - 1]) continue;
            list.add(nums[i]);
            getSubset(i + 1, nums, list, result);
            list.removeLast();
        }
    }
}