1
\$\begingroup\$

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

Link to the judge: LINK

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?

\$\endgroup\$
4
  • \$\begingroup\$ It's more like your algorithm is O(2^N * N^2) \$\endgroup\$ – Anatolii May 4 at 19:59
  • \$\begingroup\$ @Anatolii Why not the TC I said ? Can you elaborate please? \$\endgroup\$ – Shubham Prashar May 5 at 12:12
  • \$\begingroup\$ 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) \$\endgroup\$ – Anatolii May 5 at 12:34
  • \$\begingroup\$ Perhaps this would help: subsets of a multiset. \$\endgroup\$ – RootTwo May 7 at 0:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.