Subsets

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.

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

Tracing nums = [1,2,3] as a decision tree — every node visited is itself a complete subset, recorded the instant we arrive:

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).