Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Record every prefix before extending it: The Power Set.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Subset backtracking matches the clues
- 2Keep this true after every move: path contains selected values in original index order and every extension uses a later index
- 3Reach the result within O(n times 2^n) output time
Rules and pressure
- Target cost: O(n times 2^n) output time
- State rule: path contains selected values in original index order and every extension uses a later index
Lesson 1 of 3
Live algorithm trace
Subset backtracking
Complete execution1 of 5
1
choice
2
3
0
1
2
Record the empty subset before taking any value.
1
record a copy of path2
for index from start to end3
append nums[index]4
search(index + 1)5
pop to undo6
return all recorded pathspath = []output = [[]]
Truth to preserve / Cost target
Truth to preserve
path contains selected values in original index order and every extension uses a later index
Cost target
O(n times 2^n) output time
A recursive path is already one valid subset. Record it, then extend only with later indices so each subset has one increasing-index construction.
Your call · What should guide every step of this algorithm?