LeetCode 78 ·
Medium
Subsets
Return all subsets of a set of distinct integers.
Try it
Step through the core mechanic. The simulator below runs the backtracking shape this problem is built on.
Interactive · Recursion call tree — Fibonacci naive recomputes; memoised short-circuits on cache hits
Mode O(2ⁿ) calls
enter fib(6)
total calls1 unique values≤ 7 modenaive
Toggle the modes.
Naive at n=6 makes 25 calls. Memoised at n=6 makes 11 calls — and the cache
hits (amber circles) are the difference. The shape of the tree changes
dramatically: naive is a fat exponential tree; memoised collapses to a
near-linear path with stub returns where the cache hits.
The approach
Backtrack: at each index choose to include or skip the element, recording the running subset at every node. 2ⁿ subsets, built by include/exclude branching.
| Aspect | Value |
|---|---|
| Pattern | Backtracking |
| Recognise it by | Enumerate the power set. |
| Time complexity | O(n·2ⁿ) |
| Space complexity | O(n) |
| Difficulty | Medium |
Who asks it
Companies known to ask this problem, from public LeetCode company-tag aggregations. A signal of where to expect it, not a guarantee.