Description

LeetCode 90

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: [1,2,2]
Output:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Analysis

Subset problem has not only one solution. The easiest solution is bit method. Just use the bit shifting operation to list the subsets. However, the solution just works for the set that has no duplicates.

If the set has duplicates, we have to use backtracking. Because we don’t have to consider about the sequence for the set problem, we can first sort the set. Then we could comparing one element with its past element to judge if it is a duplicate. We should not add the duplicate to the result except it appears the first time in the remaining elements, that is to say, if the first duplicate has been added to the result, we could add the second duplicate. But if the first has been removed from the result after backtracking, we could not add the second duplicate.

The time is \(O(2^n)\) and the space is \(O(n)\).

Solution

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res=new ArrayList<>();
        if(nums.length==0) return res;
        Arrays.sort(nums);
        helper(res,new ArrayList<>(),nums,0);
        return res;
    }
    public void helper(List<List<Integer>> res,List<Integer> tmp,int[] nums,int cur)
    {
        res.add(new ArrayList<>(tmp));
        for(int i=cur;i<nums.length;i++)
        {
            if(i==cur||nums[i-1]!=nums[i])
            {
                tmp.add(nums[i]);
                helper(res,tmp,nums,i+1);
                tmp.remove(tmp.size()-1);
            }
        }
    }
}

Reference

[1] https://www.youtube.com/watch?v=lCvL8htQ1iI

Leave a Reply

Your email address will not be published. Required fields are marked *