Backtracking & Exhaustive Search

def subsets_with_dup(nums: list[int]) -> list[list[int]]:
    nums.sort()  # Sorting is mandatory to group duplicates for pruning
    result = []
    
    def backtrack(start: int, path: list[int]) -> None:
        # Every node in the decision tree is a valid subset
        result.append(list(path))  # Important: copy current path!
        
        for i in range(start, len(nums)):
            # Prune duplicate branches at the same tree level
            if i > start and nums[i] == nums[i - 1]:
                continue
                
            path.append(nums[i])        # Make choice
            backtrack(i + 1, path)      # Explore choice (i + 1 prevents reuse)
            path.pop()                  # Undo choice (backtrack)
            
    backtrack(0, [])
    return result