Subsets (LeetCode 78)
You are given an array nums of different integers. Return every subset of it: the empty subset, every subset in between, and the whole array. No subset may appear twice. You may return the subsets in any order.
Worked Examples
nums = [1,2,3][[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]nums = [0][[],[0]]⚖️Formal Constraints & Bounds
1 <= nums.length <= 10-10 <= nums[i] <= 10All the numbers of
numsare unique.
Core Insight
Every node of the decision tree is a valid subset, so the code saves a copy of path at every call, and the loop picks only later indices so each subset has one order.
Real-World Scenario & Production Applications
Testing every on/off combination of a small set of feature flags is the same problem: each flag is either in the combination or out of it.
Step-by-Step Execution Trace Table
backtrack(0) path = [] -> save [] pick 1 path = [1] -> save [1] pick 2 path = [1, 2] -> save [1, 2] pick 3 path = [1, 2, 3] -> save [1, 2, 3] pick 3 path = [1, 3] -> save [1, 3] pick 2 path = [2] -> save [2] pick 3 path = [2, 3] -> save [2, 3] pick 3 path = [3] -> save [3] Step-by-Step Decision Trace
- Step 1 (first call):
path = []. The call saves[]before it tries any choice. - Step 2 (pick 1):
path = [1]. The next call starts at index 1 and saves[1]. - Step 3 (pick 2, then 3): the calls save
[1, 2]and[1, 2, 3]. After each branch,path.pop()removes the last number. - Step 4 (back at
[1], pick 3):path = [1, 3]is saved. - Step 5 (back at the first call, pick 2, then 3): the calls save
[2]and[2, 3]. - Step 6 (pick 3):
[3]is saved.
Search complete: 8 subsets saved, one for each node of the tree.
nums = [1,2,3]Expected:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]| 1 | results = [], path = [] |
| 2 | def backtrack(start): |
| 3 | results.append(list(path)) |
| 4 | for i in range(start, len(nums)): |
| 5 | path.append(nums[i]) |
| 6 | backtrack(i + 1) |
| 7 | path.pop() |
| 8 | backtrack(0) |
| 9 | return results |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Backtracking is a systematic method for exploring large, combinatorial decision spaces. Where simple iteration scans a flat list, backtracking explores a tree of potential choices where every node represents a decision frame. The foundational triad of the pattern is Choose, Explore, Un-Choose:
- Choose: Select a candidate element and add it to the active path.
- Explore: Recurse down the branch to evaluate all consequences of that choice.
- Un-Choose: Symmetrically remove the candidate from the path before returning to the parent, leaving zero trace of the experiment.
For the power set (Subsets), we use a forward-advancing
startindex: each recursive step decides which remaining elements to include, naturally generating all unique subsets without generating duplicate permutations.
🏟️ The Analogy: Packing a Backpack for a Weekend Hike
Imagine packing a small backpack from a table of gear: a flashlight, a compass, and a camera. You start with an empty pack (Subset 1: []). You add the flashlight (Subset 2: ["flashlight"]). Keeping the flashlight in, you add the compass (Subset 3: ["flashlight", "compass"]). Keeping both, you add the camera (Subset 4: ["flashlight", "compass", "camera"]). You have reached the end of the table. You remove the camera (un-choose), remove the compass (un-choose), and try adding just the camera (Subset 5: ["flashlight", "camera"]). You unpack and repack one item at a time until every possible gear combination has been cataloged.
🔑 Why It Works
Notice results.append(path[:]). If you write results.append(path), Python stores a reference to the single mutable list. As backtracking unwinds, path.pop() empties that list, leaving results filled with empty arrays [[], [], ...]. Taking a snapshot path[:] freezes the state in amber.
Appending live
pathreference instead of shallow copy:results.append(path)stores a reference to the mutable list. When backtracking empties the list withpath.pop(), all elements inresultsbecome empty lists[]. Always appendpath[:]orlist(path).Duplicate subsets from unsorted inputs: If inputs contain duplicates, subsets will generate duplicate combinations unless inputs are sorted and sibling duplicates skipped.
Recursion stack depth exceeding limits: For , subsets exceed time and memory bounds. Ensure .
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
The statement asks for "all possible subsets (the power set)" of an array of different integers, and caps nums.length at 10. Every subset is wanted, including the empty one, so the answer is a list of lists and the input is small.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: path always holds exactly the choices from the root to the current node, and path is put back to its state before the call when backtrack returns. Every node is a valid subset, so backtrack saves a copy of path as soon as it is entered.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Saving
pathand notlist(path):pathis one list thatappendandpopkeep changing, so every saved subset ends up empty.Calling
backtrack(start + 1)and notbacktrack(i + 1): the next call can pick the same index again, so a value appears twice in a subset.Forgetting
path.pop():pathkeeps the old choice, and every later subset holds a wrong item.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use Subsets. Every node of the decision tree is a valid subset, so backtrack(start) saves a copy of path as soon as it is entered, including the empty one at the first call. The loop picks only indices from start onward and recurses with i + 1, so each subset is built in one order and saved once. After each branch I pop the choice, so path is the same as before it. There are 2^N nodes and each copies path in up to
O(N), so the time is O(N * 2^N) and the stack isO(N)deep."
Complexity & Mathematical Proof
O(2^N · N)
There is one call of backtrack for each subset, so 2^N calls. Each call copies path into results, which costs up to N.
O(N) Call Stack
The recursion stack is at most N calls deep, and path holds at most N numbers. The saved subsets are the output and are not counted.
T(N) = 2^N · O(N) = O(2^N · N)
Derivation Progression
2^N calls
Each call of backtrack saves one subset and loops over the later indices, so there is exactly one call for each of the 2^N subsets.
up to N values
Each call copies path into results, which costs up to N values.
Variable Definitions
Number of elements in the input array
Memory Architecture & Bounds
O(N) Call stack depth
O(N) Current subset path buffer
O(2^N · N) Array of all subsets
Boundary Best / Worst Cases
: every input of N different numbers has the same 2^N subsets
Decision & State-Space Search Tree
Senior SWE Deconstruction & Hardware Caveats
Senior SWEs mutate shared accumulator state in-place (e.g. path.append(x) followed by path.pop()) rather than cloning arrays at each recursive node. Cloning arrays at depth D creates O(2^D) temporary heap objects, destroying CPU cache and triggering massive Garbage Collection pauses.
Because backtracking recursion depth is strictly bounded by N (e.g. N <= 20 for combinations), the call stack consumes negligible memory (< a few kilobytes), fitting entirely inside L1 CPU instruction and data caches.
Subsets (LeetCode 78)
You are given an array nums of different integers. Return every subset of it: the empty subset, every subset in between, and the whole array. No subset may appear twice. You may return the subsets in any order.
Worked Examples
nums = [1,2,3][[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]nums = [0][[],[0]]⚖️Formal Constraints & Bounds
1 <= nums.length <= 10-10 <= nums[i] <= 10All the numbers of
numsare unique.
Core Insight
Every node of the decision tree is a valid subset, so the code saves a copy of path at every call, and the loop picks only later indices so each subset has one order.
Real-World Scenario & Production Applications
Testing every on/off combination of a small set of feature flags is the same problem: each flag is either in the combination or out of it.
Step-by-Step Execution Trace Table
backtrack(0) path = [] -> save [] pick 1 path = [1] -> save [1] pick 2 path = [1, 2] -> save [1, 2] pick 3 path = [1, 2, 3] -> save [1, 2, 3] pick 3 path = [1, 3] -> save [1, 3] pick 2 path = [2] -> save [2] pick 3 path = [2, 3] -> save [2, 3] pick 3 path = [3] -> save [3] Step-by-Step Decision Trace
- Step 1 (first call):
path = []. The call saves[]before it tries any choice. - Step 2 (pick 1):
path = [1]. The next call starts at index 1 and saves[1]. - Step 3 (pick 2, then 3): the calls save
[1, 2]and[1, 2, 3]. After each branch,path.pop()removes the last number. - Step 4 (back at
[1], pick 3):path = [1, 3]is saved. - Step 5 (back at the first call, pick 2, then 3): the calls save
[2]and[2, 3]. - Step 6 (pick 3):
[3]is saved.
Search complete: 8 subsets saved, one for each node of the tree.
nums = [1,2,3]Expected:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]| 1 | results = [], path = [] |
| 2 | def backtrack(start): |
| 3 | results.append(list(path)) |
| 4 | for i in range(start, len(nums)): |
| 5 | path.append(nums[i]) |
| 6 | backtrack(i + 1) |
| 7 | path.pop() |
| 8 | backtrack(0) |
| 9 | return results |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Backtracking is a systematic method for exploring large, combinatorial decision spaces. Where simple iteration scans a flat list, backtracking explores a tree of potential choices where every node represents a decision frame. The foundational triad of the pattern is Choose, Explore, Un-Choose:
- Choose: Select a candidate element and add it to the active path.
- Explore: Recurse down the branch to evaluate all consequences of that choice.
- Un-Choose: Symmetrically remove the candidate from the path before returning to the parent, leaving zero trace of the experiment.
For the power set (Subsets), we use a forward-advancing
startindex: each recursive step decides which remaining elements to include, naturally generating all unique subsets without generating duplicate permutations.
🏟️ The Analogy: Packing a Backpack for a Weekend Hike
Imagine packing a small backpack from a table of gear: a flashlight, a compass, and a camera. You start with an empty pack (Subset 1: []). You add the flashlight (Subset 2: ["flashlight"]). Keeping the flashlight in, you add the compass (Subset 3: ["flashlight", "compass"]). Keeping both, you add the camera (Subset 4: ["flashlight", "compass", "camera"]). You have reached the end of the table. You remove the camera (un-choose), remove the compass (un-choose), and try adding just the camera (Subset 5: ["flashlight", "camera"]). You unpack and repack one item at a time until every possible gear combination has been cataloged.
🔑 Why It Works
Notice results.append(path[:]). If you write results.append(path), Python stores a reference to the single mutable list. As backtracking unwinds, path.pop() empties that list, leaving results filled with empty arrays [[], [], ...]. Taking a snapshot path[:] freezes the state in amber.
Appending live
pathreference instead of shallow copy:results.append(path)stores a reference to the mutable list. When backtracking empties the list withpath.pop(), all elements inresultsbecome empty lists[]. Always appendpath[:]orlist(path).Duplicate subsets from unsorted inputs: If inputs contain duplicates, subsets will generate duplicate combinations unless inputs are sorted and sibling duplicates skipped.
Recursion stack depth exceeding limits: For , subsets exceed time and memory bounds. Ensure .
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
The statement asks for "all possible subsets (the power set)" of an array of different integers, and caps nums.length at 10. Every subset is wanted, including the empty one, so the answer is a list of lists and the input is small.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: path always holds exactly the choices from the root to the current node, and path is put back to its state before the call when backtrack returns. Every node is a valid subset, so backtrack saves a copy of path as soon as it is entered.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Saving
pathand notlist(path):pathis one list thatappendandpopkeep changing, so every saved subset ends up empty.Calling
backtrack(start + 1)and notbacktrack(i + 1): the next call can pick the same index again, so a value appears twice in a subset.Forgetting
path.pop():pathkeeps the old choice, and every later subset holds a wrong item.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use Subsets. Every node of the decision tree is a valid subset, so backtrack(start) saves a copy of path as soon as it is entered, including the empty one at the first call. The loop picks only indices from start onward and recurses with i + 1, so each subset is built in one order and saved once. After each branch I pop the choice, so path is the same as before it. There are 2^N nodes and each copies path in up to
O(N), so the time is O(N * 2^N) and the stack isO(N)deep."
Complexity & Mathematical Proof
O(2^N · N)
There is one call of backtrack for each subset, so 2^N calls. Each call copies path into results, which costs up to N.
O(N) Call Stack
The recursion stack is at most N calls deep, and path holds at most N numbers. The saved subsets are the output and are not counted.
T(N) = 2^N · O(N) = O(2^N · N)
Derivation Progression
2^N calls
Each call of backtrack saves one subset and loops over the later indices, so there is exactly one call for each of the 2^N subsets.
up to N values
Each call copies path into results, which costs up to N values.
Variable Definitions
Number of elements in the input array
Memory Architecture & Bounds
O(N) Call stack depth
O(N) Current subset path buffer
O(2^N · N) Array of all subsets
Boundary Best / Worst Cases
: every input of N different numbers has the same 2^N subsets
Decision & State-Space Search Tree
Senior SWE Deconstruction & Hardware Caveats
Senior SWEs mutate shared accumulator state in-place (e.g. path.append(x) followed by path.pop()) rather than cloning arrays at each recursive node. Cloning arrays at depth D creates O(2^D) temporary heap objects, destroying CPU cache and triggering massive Garbage Collection pauses.
Because backtracking recursion depth is strictly bounded by N (e.g. N <= 20 for combinations), the call stack consumes negligible memory (< a few kilobytes), fitting entirely inside L1 CPU instruction and data caches.