Subsets

Every element is either in a subset or out of it, so a size-n array has 2^n subsets. The two approaches below differ in how they enumerate them.

Bitmask Enumeration

Time O(n · 2^n)Space O(n · 2^n)

Every subset corresponds to one of the 2^n binary numbers from 0 to 2^n - 1: bit i set means nums[i] is included.

class Solution:
    def subsets(self, nums: list[int]) -> list[list[int]]:
        n = len(nums)
        result = []
        for mask in range(1 << n):
            result.append([nums[i] for i in range(n) if mask & (1 << i)])
        return result

Simple and iterative, but it is really the same brute force as backtracking — it just encodes the same “in or out” decisions as bits instead of recursive calls. 2^n masks, each built in O(n), giving O(n · 2^n) time and space for the output.

Backtracking (Include/Exclude via a Start Index)

OptimalTime O(n · 2^n)Space O(n)

Treat the current path as a subset that is already valid on its own — add it to the result immediately, then extend it by trying every element after start. Each recursive call decides “add this element, recurse, then remove it” (backtrack) before moving to the next candidate.

class Solution:
    def subsets(self, nums: list[int]) -> list[list[int]]:
        result = []
        path = []

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

        backtrack(0)
        return result

Trace nums = [1,2,3]. Watch the path stack: every arrival records a subset, and each pop is the backtrack that frees the slot so the next sibling can start clean.

Input nums

record

123

start = 0 — indices left of it are off-limits for this frame

Path (current subset)

····

Recorded subsets1 / 8

[]·······

1 / 15

currentdiscardedresult

Record the empty path. It is already a valid subset, so record it on arrival before extending.

Complexity: the recursion tree has exactly 2^n nodes (one per subset), each doing O(n) work to copy path into the result → O(n · 2^n) time. The path list and recursion depth are bounded by n → O(n) auxiliary space (excluding the output itself).

Bitmask Enumeration

Backtracking (Include/Exclude via a Start Index)

More Backtracking practice