LC90. Subsets II

class Solution:
    def subsetsWithDup(self, A: List[int]) -> List[List[int]]:
        """tc O(N*2^N)  sc O(N*2^N)
        1. sort the array
        2. in recursion function, when it comes to same value, skip 
        """
        res = []
        A.sort()
        def btr(start,path):
            res.append(path[:])
            for i in range(start,len(A)):
                # note here use i>start instead of i > 0, otherwise we will miss cases where duplicate need to be taken as combination 
                if i > 0 and A[i]== A[i-1]: 
                    continue
                path.append(A[i])
                btr(i+1,path)
                path.pop()

                 
        btr(0,[])
        return res