Subsets II

Duplicates turn position-based choices into repeated value-based answers. You can clean them up afterward, or stop duplicate branches before they grow.

Bitmasks + deduplication

Use a bitmask, an integer whose binary digits choose input positions, to generate all 2^n position subsets. Store each sorted subset as a canonical key — one standard tuple representation used to recognize equivalent answers.

def subsets_with_dup(nums: list[int]) -> list[list[int]]:
    values = sorted(nums)
    seen: set[tuple[int, ...]] = set()
 
    for mask in range(1 << len(values)):
        subset = tuple(
            values[i]
            for i in range(len(values))
            if mask & (1 << i)
        )
        seen.add(subset)
 
    return [list(subset) for subset in seen]

This is hard to get wrong, but repeated values can make it do enormous amounts of work for answers the set immediately throws away.

Time O(n · 2^n). Space O(n · 2^n) in the worst case, including the returned subsets and their deduplication keys.

Skip duplicate siblings — backtracking

Backtracking chooses a value, explores below it, then un-chooses it. The partial answers form a solution-space tree, a tree whose branches are candidate choices. After sorting, equal values beside each other would create identical sibling branches — branches leaving the same partial answer — so keep only the first. This is the choose/explore/un-choose backtracking pattern with one duplicate-aware guard.

def subsets_with_dup(nums: list[int]) -> list[list[int]]:
    values = sorted(nums)
    answer: list[list[int]] = []
    path: list[int] = []
 
    def search(start: int) -> None:
        answer.append(path.copy())
 
        for i in range(start, len(values)):
            if i > start and values[i] == values[i - 1]:
                continue
 
            path.append(values[i])  # choose
            search(i + 1)           # explore
            path.pop()              # un-choose
 
    search(0)
    return answer

The condition i > start is the hinge. It skips a repeated choice only when the earlier copy was available at this same depth. Once one copy is already in path, recursion starts deeper, so another equal value may be chosen and [2, 2] survives.

Time O(n · 2^n). Space O(n · 2^n) for the worst-case output, with O(n) auxiliary recursion and path space. Duplicate-heavy inputs visit far fewer branches than the bitmask baseline.