Subsets

Signal

"Return every possible subset" is the purest include-or-exclude backtracking shape — each element is independently either in the current subset or not, so the search tree branches twice per element and has exactly 2^n leaves.

Approach

Walk the elements from a start index. At each call, record the current partial path as one valid subset (every prefix of the recursion is itself a subset), then loop forward from the start index: include the element, recurse from the next index, then remove it again — backtrack — before trying the next one.

Skeleton

def backtrack(start, path):
    results.append(copy of path)
    for i in range(start, len(nums)):
        path.append(nums[i])
        backtrack(i + 1, path)
        path.pop()

Solution

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

    def backtrack(start: int) -> None:
        results.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()

    backtrack(0)
    return results

Complexity

O(n · 2^n) time and space — there are 2^n subsets, and copying each one costs up to O(n); the recursion stack itself only goes O(n) deep.

Pitfalls

• Appending path instead of path[:] — without the copy, every recorded subset is the same list object, and later mutations retroactively corrupt every previously "saved" answer.
• Starting the inner loop at 0 instead of start — that generates every subset multiple times, once per ordering of its elements, instead of once.
• Forgetting path.pop() after the recursive call — skipping the undo leaks state from one branch into its siblings.