[LeetCode] 90. Subsets II

Problem : https://leetcode.com/problems/subsets-ii/

Consider the code is traversing a tree. On each step, the code has 2 options that are pick or not pick number on this position.

Time Complexity =  O ( len(nums) * len(nums) * log (len(nums) )  )

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = []
        
        def backtracking(start, partial, maxSize):
            if len(partial) == maxSize:
                result.append(partial)
                return
            
            for i in range(start, len(nums)):
                # value of number[i-1] has been picked
                # skip number[i-1] to avoid duplicate subsets
                if i > start and nums[i] == nums[i-1]:
                    continue
                    
                backtracking(i + 1, partial + [nums[i]], maxSize)
        
        
        for i in range(len(nums)+1):
            backtracking(0, [], i)
            
        
        return result

An iterative solution which uses hashset to filter the duplicates.

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        result = set([()])
        nums.sort()
                
        for i, n in enumerate(nums):
            tmp = result.copy()
            for prefix in tmp:
                result.add(prefix + (n,))
                       
        return result

Edited on 08/03/2021. Add the hashset based iterative solution.