# Generating Unique Subsets using Bitmasking

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(2^N)\$$ however according to me, my code's time complexity is $$\O(2^N\log{N})\$$ as the for loop runs $$\2^N\$$ times and inside that we are checking all the $$\\log{N}\$$ bits. Can I reduce the time complexity to $$\2^N\$$? or is it not possible to reduce the time complexity while solving the problem using bitmasking?

• It's more like your algorithm is O(2^N * N^2) – Anatolii May 4 at 19:59
• @Anatolii Why not the TC I said ? Can you elaborate please? – Shubham Prashar May 5 at 12:12
• Because your ans = sorted(ans) is O((2^n)*log(2^n)*(cost of a single compare operation)). Cost of a compare operation is O(n) because elements in ans are not single integers - they're lists. Hence, the total time complexity is O(2^n*n^2) – Anatolii May 5 at 12:34
• Perhaps this would help: subsets of a multiset. – RootTwo May 7 at 0:58