FAANG · LeetCode #78

Subsets — three-stage drill

1The ProblemMedium

Subsets

Return every possible subset (the power set) of a list of distinct integers.

Examples

[1,2,3]→ [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]][0]→ [[], [0]]

constraintAll numbers are distinct; the answer may be returned in any order.

2The PatternTIME O(n · 2ⁿ) · SPACE O(n)

Backtracking

Build a candidate one choice at a time, exploring every branch of the decision tree. When a path is complete (or dead), un-choose the last step and try the next — a DFS that always cleans up after itself.

Problems using this pattern

3The SolutionRESULT → 8 subsets

Step through it

record the empty subset → []

Step 1 / 23

Python▎record on entry · choose → recurse → un-choose for each remaining index

1def subsets(nums):
2    res = []
3    path = []
4 
5    def backtrack(start):
6        res.append(path[:])            # record the current subset
7        for i in range(start, len(nums)):
8            path.append(nums[i])       # choose nums[i]
9            backtrack(i + 1)           # explore with the rest
10            path.pop()                 # un-choose, try the next
11 
12    backtrack(0)
13    return res

why it worksWalk a decision tree: at each index, you either include nums[i] in the current path or not. backtrack(start) first RECORDS the path as a finished subset, then for every remaining index it CHOOSES that number, recurses, and UN-CHOOSES (pops) before trying the next. The pop is what lets one shared `path` array explore every branch. 2ⁿ subsets, each up to length n → O(n · 2ⁿ).

Arrow keys to navigate · escape to reset

All problems by pattern

Two Pointers

Sliding Window

Prefix Sum

Monotonic Deque

Shortest Subarray with Sum at Least K

Binary Search

Arrays & Hashing

Monotonic Stack

Intervals

Subsets — three-stage drill

Subsets

Backtracking

Step through it

All problems by pattern

Two Pointers

Sliding Window

Prefix Sum

Monotonic Deque

Binary Search

Arrays & Hashing

Monotonic Stack

Intervals

Heap / Top-K

Backtracking

Recursive Descent