90. Subsets II

Description

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

Solution

DFS

跟Subsets相同的思路，注意对重复元素的处理。

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> subsets = new ArrayList<>();
        if (nums == null || nums.length < 1) return subsets;
        
        Arrays.sort(nums);
        List<Integer> subset = new ArrayList<>();
        subsetsRecur(nums, 0, subset, subsets);
        return subsets;
    }
    
    public void subsetsRecur(int[] nums, int begin, List<Integer> subset,
                            List<List<Integer>> subsets) {
        subsets.add(new ArrayList<>(subset));
        for (int i = begin; i < nums.length; ++i) {
            if (i > begin && nums[i] == nums[i - 1]) continue;  // skip duplicates
            subset.add(nums[i]);
            subsetsRecur(nums, i + 1, subset, subsets);
            subset.remove(subset.size() - 1);
        }
    }
}

或者这样写：

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> subsets = new ArrayList<>();
        if (nums == null || nums.length < 1) {
            return subsets;
        }
        
        Arrays.sort(nums);
        subsetsRecur(nums, 0, new ArrayList<>(), subsets);
        return subsets;
    }
    
    public void subsetsRecur(int[] nums, int i, List<Integer> subset
                             , List<List<Integer>> subsets) {
        if (i >= nums.length) {
            subsets.add(new ArrayList<>(subset));
            return;
        }
        
        int count = 1;
        while (i + count < nums.length && nums[i + count] == nums[i]) {
            ++count;
        }
        
        subsetsRecur(nums, i + count, subset, subsets);
        
        for (int k = 0; k < count; ++k) {
            subset.add(nums[i]);
            subsetsRecur(nums, i + count, subset, subsets);
        }
        
        while (count-- > 0) {
            subset.remove(subset.size() - 1);
        }
    }
}