90. Subsets II

Description

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.

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: [1, 2, 2]

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

Example 2

Input: [4, 1, 2, 2]

Output: [ [], [1], [1, 2], [2], [1, 2, 2], [2, 2], [1, 2, 2, 4], [1, 2, 4], [1, 4], [2, 2, 4], [2, 4], [4] ]

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> subsets = new ArrayList<>();
        Arrays.sort(nums);
        backtrack(subsets, new LinkedList<Integer>(), nums, 0);
        return subsets;
    }

    private void backtrack(List<List<Integer>> subsets,
                          LinkedList<Integer> subset,
                          int[] nums,
                          int index) {
        subsets.add(new ArrayList(subset));
        for(int i = index; i < nums.length; i++) {
            if (i > index && nums[i-1] == nums[i]) continue;
            subset.add(nums[i]);
            backtrack(subsets, subset, nums, i+1);
            subset.removeLast();
        }
    }
}

Solution 2

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> subsets = new ArrayList<>();
        subsets.add(new ArrayList());
        
        Arrays.sort(nums);
        
        for(int i = 0, start = 0, end = 0; i < nums.length; i++) {
            start = 0;
            
            if(i > 0 && nums[i-1] == nums[i]) {
                start = end+1;
            }
            
            end = subsets.size()-1;

            for(int j = start; j <= end; j++) {
                List<Integer> subset = new ArrayList(subsets.get(j));
                subset.add(nums[i]);
                subsets.add(subset);
            }
        }
        return subsets;
    }
}

Follow up