90. Subsets II

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)

--

--

--

Tech-Enthusiast, Coder,Explorer,Geeky,Software Engineer |A piece of code delivers everything that you need. The world is all about codes.

Love podcasts or audiobooks? Learn on the go with our new app.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Dhanarajappu

Dhanarajappu

Tech-Enthusiast, Coder,Explorer,Geeky,Software Engineer |A piece of code delivers everything that you need. The world is all about codes.

More from Medium