Pattern this teaches:Backtracking Basics
Subsets
A medium Backtracking interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Backtracking
- Sheets
- 3
- Core for
- 0 roles
The problem
The array holds distinct integers. Return every subset you can form from it, from the empty set up to the whole array, each exactly once, in any order.
Example 1
- Input
- nums = [2,1,3]
- Output
- [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
- Why
- All 8 subsets of {1,2,3} sorted by size then lexicographically.
Example 2
- Input
- nums = [0]
- Output
- [[], [0]]
- Why
- The power set of {0} contains 2 subsets: the empty set and the set containing 0.
Constraints
- 1 <= nums.length <= 10
- -10 <= nums[i] <= 10
- All numbers in nums are distinct
How to think about it
Updated 2026-09-29Every element in the array faces an independent binary decision: either it joins the subset or it stays out. Viewing the power set as a full binary decision tree of depth n reveals that every leaf is a valid subset, meaning you never need to prune or search for a target; you only record what you hold at each step.
Approaches, worst first
Cascading iterative addition
time O(n * 2^n) · space O(n * 2^n)
Start with an empty subset. For every number in the input, clone every existing subset, append the number to the clones, and merge them back. Simple to trace, but requires frequent reallocation and copying of intermediate lists.
Bitmask iteration
time O(n * 2^n) · space O(1)
Map each integer from 0 to 2^n - 1 to a subset where the j-th bit indicates inclusion of nums[j]. Non-recursive and avoids call stack overhead, but tests n bits for every single subset even when most bits are zero.
Backtracking pick or skipWrite this one
time O(n * 2^n) · space O(n)
Maintain a single mutable buffer. At index i, branch into skipping nums[i] and taking nums[i], snapshotting the buffer once reaching index n. Mutating in place keeps extra working memory strictly bounded by the recursion depth.
Where people lose marks · 3
- Pushing a reference of the working list directly into the output instead of a shallow copy. Because the same list is mutated and emptied later, every captured subset ends up empty.
- Forgetting to pop the element after exploring the branch that included it, which bleeds elements into sibling branches.
- Overlooking the base subset: an empty list is a required member of the power set and must be recorded when recursion reaches the end without choices.
The theory behind it
Backtracking — the ground this problem stands on. All Backtracking problems
What Backtracking is
Backtracking is an organized trial-and-error search through a maze of possibilities. You make a tentative choice, move forward to explore where that path leads, and if you hit a dead end or finish finding an answer, you back up and undo that choice. By cleaning up your changes before trying the next option, a single shared board or list is explored thoroughly without needing to clone full copies of your data at every turn.
When to reach for it
Reach for backtracking when a problem asks to generate all possible solutions, like all subsets, permutations, valid parentheses combinations, or word search paths on a board. Signals include puzzles with strict constraint rules, like placing eight non-attacking queens on a chessboard or solving a Sudoku grid. Whenever you must construct combinations step by step and abandon dead-end branches early before wasting time exploring impossible paths, use backtracking.
How the pattern works
Follow a three-step rhythm inside a loop: choose, explore, and unchoose. First, check if the current state satisfies your goal; if so, save a copy of it and return. Next, prune illegal moves immediately using constraint checks so unpromising branches are skipped. For each valid candidate, apply the move to your shared path or board, call the recursive function to explore deeper, and finally undo the move right after the call returns. Undoing restores the shared state so sibling choices start from a clean slate.
More Backtracking problems
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .