Solution Space Trees
See the whole search space as a tree: one decision per level, and 2^n leaves that are the answers.
Examples
The eight leaves, read left to right: taking a number goes left, leaving it goes right.
One decision, two leaves. Any order is accepted.
What is a Solution Space Tree?
A solution space tree is the whole set of candidates a problem admits, drawn as a tree. Backtracking never builds it — it walks it, depth first, one branch at a time.
Taking subsets of [1, 2, 3] as the example, and asking one question per level — do I take this number? — gives:
- Root: nothing decided yet, the candidate is
[]. - Level i: the decision about
nums[i], so the tree is exactly as deep as the input is long. - A node: a partial candidate — some numbers decided, the rest still open.
- A leaf: every number decided, so the candidate is complete. There are 2ⁿ of them, and they are the answer.
Why Visualize as a Tree?
Backtracking is fundamentally a Depth-First Search (DFS) on this implicit tree. By visualizing it this way, abstract recursive calls become concrete moves:
- Recursive Call: Moving DOWN an edge to a child node.
- Base Case: Reaching a Leaf node.
- Return Statement (Backtrack): Moving UP to the parent node to try a different branch.
Interactive Visualization
The same subsets as the introduction lesson, and the same LeetCode problem — but one decision per level, so the shape of the search is the thing on screen. A left branch takes the number at that depth (+2), a right branch leaves it (−2), and the line under a node is the candidate so far. Only the leaves are recorded, which is why the count beside the figure climbs to 2ⁿ and no further.
Pruning (The Power of Backtracking)
Subsets has nothing to prune — every leaf is a valid answer, which is exactly why it is the clearest picture of a solution space.
Pruning is what the later lessons add. When a problem has a constraint, a node can be rejected before its children are ever created:
- Combination Sum: once the running total passes the target, no deeper choice can bring it back.
- N-Queens: once two queens share a diagonal, nothing below that node is valid.
The saving is the whole subtree, not one node — which is why backtracking beats generating every candidate and filtering afterwards, even though both explore the same space in the worst case.
The Solution: One Decision per Level
The same problem as the introduction lesson, written as one decision per level (LeetCode 78).
Solution Space Trees Code
1var subsets = function(nums) {2 const result = [];3 const path = [];45 const backtrack = (i) => {6 if (i === nums.length) {7 result.push([...path]);8 return;9 }10 path.push(nums[i]);11 backtrack(i + 1);12 path.pop();13 backtrack(i + 1);14 };1516 backtrack(0);17 return result;18};