Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Choose, explore, undo: Branching Choices.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Backtracking decision tree matches the clues
- 2Keep this true after every move: the current path contains exactly the choices for this branch
- 3Reach the result within O(2ⁿ)
Rules and pressure
- Target cost: O(2ⁿ)
- State rule: the current path contains exactly the choices for this branch
Lesson 1 of 3
Live algorithm trace
Backtracking decision tree
Complete execution1 of 7
1
choice
2
3
Record the empty subset at the decision-tree root.
1
record current path2
for each next choice3
choose and recurse4
undo the choicepath = []recorded = 1
Truth to preserve / Cost target
Truth to preserve
the current path contains exactly the choices for this branch
Cost target
O(2ⁿ)
Backtracking explores a decision tree. Add a choice, recurse into that branch, then remove the choice so the next branch starts from clean state.
Your call · What should guide every step of this algorithm?