Backtracking and subsets: time and space complexity

High interview relevanceRoadmap: Advanced

Time	O(2ⁿ) subsets; O(n · 2ⁿ) including copying each one
Space	O(n) recursion, plus stored output

Why it costs this much

Each item is either included or excluded, so there are 2ⁿ leaves in the recursion tree.

Code

def subsets(nums):
    res, cur = [], []
    def go(i):
        if i == len(nums):
            res.append(cur[:])        # 2^n leaves; each copy costs O(n)
            return
        go(i + 1)                     # exclude nums[i]
        cur.append(nums[i])
        go(i + 1)                     # include nums[i]
        cur.pop()
    go(0)
    return res

Common pitfalls

Copying each result adds a factor of n to the time. Pruning helps in practice but often does not change the worst-case bound.