Skip to content
GKgkml.dev
← Problem set
#78MediumBacktracking

Subsets

The tell: Enumerate every combination — the canonical choose/explore/un-choose template.

How you get there

  1. 1At each index, either include the element or do not.
  2. 2Record a copy of the current path at every node of the recursion tree.
  3. 3Un-choose after recursing so sibling branches start from a clean state.

Solution

Python
def subsets(nums: list[int]) -> list[list[int]]:
    out: list[list[int]] = []
    path: list[int] = []

    def backtrack(start: int) -> None:
        out.append(path[:])            # copy: path is mutated afterwards
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()                 # un-choose

    backtrack(0)
    return out
Time
O(n · 2ⁿ)
Space
O(n) excluding output

What goes wrong

Appending `path` rather than `path[:]` makes every result reference the same list, which ends up empty.

Test yourself on DSANext: Word Search →