intermediate~5h
Recursion and Backtracking Problem Set
A themed set of classic recursion and backtracking problems — factorial and Fibonacci as the gateway into exponential blowup, then subsets, permutations, N-Queens, and a simplified Sudoku solver as progressively deeper applications of the 'choose, explore, un-choose' backtracking template.
Learning objectives
- Write naive recursive solutions for factorial and Fibonacci, and explain why naive Fibonacci recursion is exponential while factorial recursion is linear
- Describe how memoization fixes the exponential blowup in naive recursive Fibonacci by caching overlapping subproblem results
- Generate all subsets of a set using the include/exclude recursive decision tree
- Generate all permutations of a string using swap-based or used-tracking backtracking
- Apply the 'choose, explore, un-choose' backtracking template to solve N-Queens, including how to prune invalid placements early
- Explain, at a conceptual level, how constraint propagation and backtracking combine to solve a Sudoku puzzle
This is a Pro chapter
Sign in, then upgrade to Pro or Power to unlock this and the full Core Java Mastery library.
Recursion and Backtracking Problem Set