Internship← Competitive Programming learning pathCompetitive Programming · Module 7 of 10
Recursion and backtracking
Explore choices step by step and undo them.
📖 Key ideas
- Recursion solves a problem through smaller copies of itself.
- Always define a base case to stop.
- Backtracking tries a choice, recurses, then undoes it.
- Generate subsets, permutations and N-Queens with backtracking.
- Prune branches that cannot lead to a valid answer.
💡 Real-life example: Backtracking is like walking a maze: at a dead end, step back to the last junction and try another path.
Base caseCondition that stops recursion
BacktrackingTry, recurse, undo
PruningSkip hopeless branches
PermutationAn ordering of items