Subsets

The output already contains 2^n subsets, so no algorithm can dodge exponential work. The useful question is how cleanly you visit every answer exactly once.

Enumerate bitmasks

A bitmask is an integer whose binary digits act like yes/no switches. Bit i tells you whether to include values[i]. The integers from 0 through 2^n - 1 cover every possible switch setting.

def subsets(nums: list[int]) -> list[list[int]]:
    values = sorted(nums)
    answer: list[list[int]] = []
 
    for mask in range(1 << len(values)):
        subset: list[int] = []
        for i, value in enumerate(values):
            if mask & (1 << i):
                subset.append(value)
        answer.append(subset)
 
    return answer

Sorting first makes every emitted subset ascending. Different masks differ at some bit, so they can't describe the same subset when the input values are distinct.

Time O(n · 2^n). Space O(n · 2^n) for the returned power set; the temporary subset uses O(n) additional space.

Choose or skip — backtracking

Backtracking is depth-first search that chooses a value, explores that choice, and then un-chooses it before trying another path. Here, each index creates two branches: include the value or skip it. Those branches form a solution-space tree, a tree whose nodes represent partial subsets. That choose/explore/un-choose cycle is the backtracking pattern.

def subsets(nums: list[int]) -> list[list[int]]:
    values = sorted(nums)
    answer: list[list[int]] = []
    path: list[int] = []
 
    def search(index: int) -> None:
        if index == len(values):
            answer.append(path.copy())
            return
 
        path.append(values[index])       # choose
        search(index + 1)                # explore
        path.pop()                       # un-choose
 
        search(index + 1)                # explore the skip branch
 
    search(0)
    return answer

Every root-to-leaf path makes one include-or-skip decision for every value, so it maps to exactly one subset. Conversely, every subset supplies one such decision path. That gives both completeness and uniqueness.

Time O(n · 2^n). Space O(n · 2^n) for the output, with O(n) auxiliary recursion and path space.