LeetCode 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. Example: Input: [1,2,2] Output: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]

Explanation

The problem is a follow-up question for Subset. It is also a typical backtracking coding problem.

We can have a recursion function to add visited subsets to the final results. Remember to make a deep copy whenever we are adding the subset to the results.

Java Solution

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
    
        if (nums == null || nums.length == 0) {
            return results;
        }
        
        Arrays.sort(nums);
        
        List<Integer> subset = new ArrayList<>();
        toFindAllSubsets(nums, results, subset, 0);
        
        return results;
    }
    
    private void toFindAllSubsets(int[] nums, List<List<Integer>> results, List<Integer> subset, int startIndex) {
        results.add(new ArrayList<>(subset));
        
        for (int i = startIndex; i < nums.length; i++) {
            if (i != startIndex && nums[i] == nums[i - 1]) {
                continue;
            }
            
            subset.add(nums[i]);
            toFindAllSubsets(nums, results, subset, i + 1);
            subset.remove(subset.size() - 1);            
        }
    }
}

Python Solution

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        results = []
        nums = sorted(nums)

        self.helper(results, [], 0, nums)
        
        return results
    
    def helper(self, results, combination, start, nums):
        if combination not in results:
            results.append(list(combination))
        
        for i in range(start, len(nums)):
            combination.append(nums[i])            
            self.helper(results, combination, i + 1, nums)            
            combination.pop()
        
        

• Time Complexity: ~N
• Space Complexity: ~N