Solutions

# Sort the array to handle duplicates, then use backtracking to generate subsets, skipping duplicates.
# backtracking

# Recursion + backtracking - O(n* 2^n) time, O(n) space (2^n subsets, and O(n) space for the recursion stack)
def subsetsWithDup(nums: list[int]) -> list[list[int]]:
    nums.sort()
    res = []

    def dfs(curr: list[int], i: int):
        if i >= len(nums):
            res.append(curr.copy())
            return
        
        curr.append(nums[i])
        dfs(curr, i+1)
        curr.pop()

        # skip duplicates
        while i+1 < len(nums) and nums[i] == nums[i+1]:
            i += 1

        dfs(curr, i+1)

    dfs([], 0)
    return res


# Brute force: generate all subsets and use a set to filter out duplicates. O(n * 2^n) time, O(n * 2^n) space
def subsetsWithDup(nums: list[int]) -> list[list[int]]:
    res = set()

    def backtrack(i, subset):
        if i == len(nums):
            res.add(tuple(subset))
            return

        subset.append(nums[i])
        backtrack(i + 1, subset)
        subset.pop()
        backtrack(i + 1, subset)

    nums.sort()
    backtrack(0, [])
    return [list(s) for s in res]