# python – Generating Unique Subsets using Bitmasking (Microsoft)

Given an array arr() of integers of size N that might contain duplicates, the task is to find all possible unique subsets.

Note: Each subset should be sorted.

Example 1:

``````Input: N = 3, arr() = {2,1,2}
Output:(),(1),(1 2),(1 2 2),(2),(2 2)
Explanation:
All possible subsets = (),(2),(1),(1,2),(2),(2,2),(2,1),(2,1,2)
After Sorting each subset = (),(2),(1),(1,2),(2),(2,2),(1,2),(1,2,2)
Unique Susbsets in Lexicographical order = (),(1),(1,2),(1,2,2),(2),(2,2)
``````

Example 2:

``````Input: N = 4, arr() = {1,2,3,3}
Output: (),(1),(1 2),(1 2 3)
(1 2 3 3),(1 3),(1 3 3),(2),(2 3)
(2 3 3),(3),(3 3)
``````

My correct and working code:

``````class Solution:

def checkSetBits(self,num,arr):
pos = 0
res = ()

while num != 0:
if num & 1 == 1:
res.append(arr(pos))
pos += 1
num = num >> 1
return res

def AllSubsets(self, arr,n):
arr = sorted(arr)
ans = ()
N = 2**len(arr)

for i in range(N):
item = self.checkSetBits(i,arr)
ans.append(item)

# removing duplicate lists
ans = sorted(ans)
i = len(ans)-1

while i > -1:
if ans(i) == ans(i-1):
ans.pop(i)
i -= 1

return ans
``````

My doubt :

The required time complexity is `O(2N)` however according to me, my code’s time complexity is `O(2NlogN)` as the `for` loop runs 2N times and inside that we are checking all the `logN` bits. Can I reduce the time complexity to `2N`? or is it not possible to reduce the time complexity while solving the problem using bitmasking?