Backtracking · Stage 1 of 3
Subsets & Include/Exclude Decisions
Branch on taking or skipping each element to explore 2^n subsets
Foundations
Backtracking explores every way to make a sequence of choices: make a choice, explore everything that follows from it, then undo it and try the next. The partial answer lives in one list, path, that grows on the way down and shrinks on the way back, choose, explore, unchoose, so nothing is copied until an answer is complete. Each choice is one recursive call deeper, as in the Recursion lessons.
For subsets, each element's choice is binary: include it or skip it. Deciding all n elements, one level of recursion each, forms a decision tree with 2^n leaves, and every leaf is a different subset. Include means append, recurse, then pop; skip means recurse without appending. Each subset is reached by exactly one path, so none repeats.
On nums = [7, 1, 5, 3, 6], include 7, skip 1, and include 5: path is [7, 5] while 3 and 6 are undecided. Including 3 leads to [7, 5, 3] and two leaves below it; popping 3 and skipping it leads to [7, 5] and two more. With five binary decisions there are 2^5 = 32 subsets.
nums
choice
path holds [7, 5]. Each undecided element doubles the leaves below this point, so 4 subsets still extend this prefix.- Open lesson
Recursion
Backtracking is recursion that undoes a choice. That lesson covers the call stack.
Case Scenario
The problem
Subsets
Return every subset of nums (the power set). Sort each subset ascending, then sort the list of subsets lexicographically, comparing element by element; a subset that is a prefix of another comes first.
- Input
- nums = [1, 2, 3]
- Output
- [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]
Subsets asks for every subset of the distinct integers in nums. Each element is in or out, so the decision tree has 2^n leaves, one per subset. For nums = [1, 2, 3], with the include branch tried first, the subsets come out as [1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], and [].
The direct approach builds each subset from scratch, for example by counting from 0 to 2^n - 1 and reading each number's bits as in-or-out choices. That works, but it rebuilds every shared prefix: [1, 2] is assembled again inside [1, 2, 3]. Backtracking keeps one path and shares each prefix with every subset below it.
Step by step
Walkthrough
Same input, now one step at a time. Each frame highlights the line that runs and the values it changes.
- 1.
choose(i): ifiequalslen(nums), record a copy ofpath. - 2.Otherwise append
nums[i], callchoose(i + 1), then pop it. - 3.Call
choose(i + 1)again, this time withoutnums[i].
Python
Subsets
- Input:
- nums = [1, 2, 3]
- Output:
- [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]
- 1def subsets(nums):
- 2 result, path = [], []
- 3 def choose(i):
- 4 if i == len(nums):
- 5 result.append(path[:])
- 6 return
- 7 path.append(nums[i])
- 8 choose(i + 1)
- 9 path.pop()
- 10 choose(i + 1)
- 11 choose(0)
- 12 return result
Calling
Each level decides one number: the left branch includes it, the right branch skips it.
The Pattern
The invariant: when choose(i) runs, path holds exactly the choices made for elements 0 to i - 1. Appending before the include branch and popping after it restores that state for the skip branch, so each of the 2^n leaves sees a different path.
From the trace
Subsets
path was one list the whole time, grown on the way down and shrunk on the way back.Check it against the walkthrough. choose(0) appended 1, choose(1) appended 2, and choose(2) appended 3; at i = 3 it recorded [1, 2, 3]. Popping 3 and taking the skip branch recorded [1, 2], and the same pop-then-skip pattern produced the other six subsets, ending with [].
path is copied only at a leaf, because later pops change the working list; every prefix is shared by both of its branches. The same include-or-skip tree builds combinations of size k, or subsets that reach a target sum, by cutting a branch once it can no longer qualify.
Complexity
TimeO(n · 2ⁿ)
SpaceO(n)
There are 2^n subsets, and copying each costs up to n, so time is O(n · 2ⁿ). No approach can do better, because that is the size of the output. Besides the output, path and the call stack hold at most n items: O(n) space.
When to use this in an interview
- The prompt asks for all subsets, all combinations, or every way to pick some elements.
- Each element makes an independent in-or-out decision.
- The output itself is exponential, so a
2^nsearch is expected.
In production
GROUP BY CUBE in SQL
PostgreSQL's GROUP BY CUBE (a, b, c) aggregates over every subset of the listed columns: all three, each pair, each single column, and none, 2^3 = 8 grouping sets. The planner expands the cube into that power set the way the walkthrough does, each column in or out, before computing the totals. A cube over n columns costs 2^n aggregations, which is why cubes stay small.
Where this breaks
Include-or-skip lists every subset. It does not stop at the first subset that sums to a target, and repeated numbers produce duplicate subsets.
Your turn
Solve it yourself
You have watched one path grow and shrink through every include-or-skip decision. Write it yourself on Subsets, then skip duplicate values in Subsets II, and let a value repeat until a target is reached in Combination Sum.
- 1Solve it
Subsets
Guided · the problem you traced above
- 2Subsets IIOn your own · same pattern, no walkthrough
- 3Combination SumOn your own · same pattern, no walkthrough