90. Subsets II

Subsets II - LeetCode

Approach 1:

Iterative Brute force

Sort the array. Then generate all subset iteratively. Remove the duplicate subset using a set.

The same approach can be done using recursion.

import copy
class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res=[[]]
        nums.sort()
        for i  in  nums:
            abc = copy.deepcopy(res)
            for j  in abc:
                j.append(i)
            res+=abc
        return [list(l) for l in  set([tuple(i) for i in res])]

Time: (n*2^n) n-> number of element in the given array.

Space: O(2^n)

Approach 2:

More intuitive way using recursion.

Here we generate 1 size subset 2 size subset and so on. But making sure no duplicates are made in each of those steps.

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        result=[]
        nums.sort()
        self.rec(0,nums,[],result)
        return result
    def rec(self,ind,nums,ds,result):
        
        result.append(ds)
        for i in range(ind,len(nums)):
            if i!=ind and nums[i]==nums[i-1]:
                continue
            self.rec(i+1,nums,ds+[nums[i]],result)

Time: (n*2^n) n-> number of element in the given array.

Space: O(2^n)