class Solution:
    # Time: O(2 ** n), space(n * 2**n)
    def generate_subsets_from_unique(self, nums):
        result = []
        self.backtrack(nums, [], 0, result)
        return result
    
    def generate_subsets_from_duplicates(self, nums):
        result = []
        nums.sort()
        self.backtrack(nums, [], 0, result)
        return result
    
    def backtrack(self, nums, prefix, start, result):
        result.append(prefix)
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i-1]:
                continue
            self.backtrack(nums, prefix + [nums[i]], i + 1, result)

solution = Solution()
nums = [1,2,3]
# nums = [1,2,2]
print(solution.generate_subsets_from_unique(nums))