Subsets

Return every subset of the input values.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Subsets: Save every current path, then recurse only to larger indices and pop the chosen value on return.

Input and goalReturn every subset of the input values.

Save the empty pathchoose(0) first copies [] into answer; indices 0, 1, and 2 remain available.

[]active callstart 0

inputnums = [1, 2, 3]columnspath | startactionsave []answer[[]]

Recognize it

Use this pattern when every combination of distinct input positions is valid and order does not matter, so each partial selection must be emitted once.

Keep true

On entry to choose(start), path contains indices in strictly increasing order, answer already contains every path visited earlier in DFS order, and only indices start or greater may extend this path.

Reuse it

When order should not create duplicates, advance a start boundary after each choice; this same skeleton generates combinations, k-subsets, and increasing-index selections.

Pattern: Backtracking with a start position.

Simple idea: Every partial path is already one valid subset. Save it. Then add each value that comes after the last chosen position.

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

   def choose(start: int) -> None:
      answer.append(path.copy())
      for index in range(start, len(nums)):
         path.append(nums[index])
         choose(index + 1)
         path.pop()

   choose(0)
   return answer

Cost: $O(n{2}^n)$ time and $O(n)$ working space, not counting the answer.