LeetCode 78 · Backtracking · concept: backtracking
Problem
Return all subsets (the power set) of an array of distinct integers.
[1,2,3] -> [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]
Approach — include/exclude each element (optimal)
The power set is a binary choice per element: take it or skip it. Backtracking explores both branches, appending a copy of the current path at each leaf.
def subsets(nums):
res = []
path = []
def backtrack(i):
if i == len(nums):
res.append(path[:]) # a completed subset (copy!)
return
path.append(nums[i]) # choice 1: include nums[i]
backtrack(i + 1)
path.pop() # undo
backtrack(i + 1) # choice 2: exclude nums[i]
backtrack(0)
return resTime O(n · 2ⁿ), space O(n) recursion (output is O(n·2ⁿ)).
The backtracking skeleton
Every backtracking solution is: choose → recurse → un-choose. The path.append(...) / path.pop() bracket a recursive call so the same list is reused across branches instead of copied. And you must append path[:] (a copy) to the result — appending path itself stores a reference that later mutations corrupt.
Key insight
Generate all combinations/subsets → binary include-exclude backtracking. Subsets is the template the whole category specializes: Combination Sum changes the branching, Subsets II adds duplicate-skipping, but the choose/recurse/undo spine is identical.
Related
- concept: backtracking
- next: Combination Sum
Software engineering
Infrastructure & security
Computer science
Hardware & engineering