Generate all subsets of a set — the power set — using backtracking.
At each step of a recursive walk through the input, you make a binary choice: include the current element or skip it. Recording the current path at every node of the recursion tree (not just the leaves) collects all 2^n subsets. A `start` index prevents duplicates by ensuring elements are only considered left-to-right.
How to think about it
Recognise the pattern
The signal is “enumerate all possible combinations / selections.” Whenever the problem asks for every valid arrangement, selection, or partition — and the answer set is exponential — backtracking is the pattern. You build candidates incrementally and “undo” a choice (backtrack) before trying the next one. For subsets specifically, there is no pruning step because every partial path is valid.
Build the approach step by step
Brute force with bitmasks works: for each integer 0 … 2^n - 1, the set bits tell you which elements to include. Clear, but harder to generalise to permutations or combinations with constraints.
The backtracking approach: think of a decision tree where at each level you decide whether to include nums[i].
nums = [1, 2, 3]
[]
/ \
[1] []
/ \ / \
[1,2] [1] [2] []
/ \ / \ / \ / \
[1,2,3][1,2][1,3][1][2,3][2][3][]Every node in this tree is a valid subset. Collect them all.
In code, backtrack(start, path) iterates from start to len(nums)-1. For each index i, it appends nums[i] to path, recurses with start=i+1, then pops nums[i] (the backtrack step). Before the loop, it records a copy of path — that is the current subset.
Complexity
- Time — O(n × 2^n): there are 2^n subsets; copying each path into the result takes O(n) worst case.
- Space — O(n): the recursion depth and the
pathlist are both at most n. The output list itself is O(n × 2^n) but that is unavoidable — we’re asked to produce every subset.