Subsets II

Medium

Given an integer array nums that may contain duplicates, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

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

Example 2:

Input: nums = [0]
Output: [[],[0]]

Constraints:

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10

Implementation

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if(nums == null || nums.length == 0){
            return result;
        }
        List<Integer> current = new ArrayList<>();
        Arrays.sort(nums);
        boolean[] used = new boolean[nums.length];
        subsetsWithDup(nums, result, current, used, 0);
        return result;
    }
    
    private void subsetsWithDup(int[] nums, List<List<Integer>> result, List<Integer> 
                current, boolean[] used, int start){
        result.add(new ArrayList<>(current));
        for(int i = start ; i< nums.length ; i++){
            if( i > start && nums[i] == nums[i-1] && !used[i-1]){
                continue;
            }
            current.add(nums[i]);
            used[i] = true;
            subsetsWithDup(nums, result, current, used, i+1);
            used[i] = false;
            current.remove(current.size() - 1);
        }
    }
}

Complexity Analysis

  • Time Complexity: O(N × 2N). 2N to generate all subsets and then O(N) to copy each set into output list.
  • Space Complexity: O(N × 2N)  to keep all the subsets of length  N, since each of elements could be present or absent.

Categories: Backtracking

Tagged as: ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s