DataslopeBacktracking
Learn choose-explore-unchoose search, pruning, and classic backtracking problems in C++
Backtracking builds a solution incrementally and abandons a candidate as soon as it cannot become valid. The template is choose → explore → un-choose.
Backtracking is disciplined recursion
Recursion calls itself; backtracking also deliberately undoes choices and prunes impossible branches.
Permutations
Subsets
Include/exclude recursion visits both decisions for each element.
Bitmask iteration is deterministic and iterative.
N-Queens
Place one queen per row. Columns and diagonals prune invalid placements.
Sudoku solver
Try digits 1 through 9 in the next empty cell, recurse, then undo if it fails.
Word search
Mark a cell visited, search neighbors, then unmark it.
Pruning techniques
Check constraints before recursing, reject partial states early, and try promising branches first. Backtracking differs from plain recursion because it explicitly manages partial choices and undoes them.
Implement std::vector<std::vector<int>> subsets(const std::vector<int>& nums). Use deterministic bitmask order from 0 to 2^n-1 so stdout matches exactly.
Implement int countNQueens(int n). The driver prints counts for n=1..6.
Implement bool exist(std::vector<std::vector<char>>& board, const std::string& word).
What is the classic backtracking pattern?
Sort -> scan -> stop.
Choose -> explore -> un-choose.
Hash -> lookup -> return.
Push all nodes into a queue.
What is pruning?
Rejecting a partial solution before exploring all descendants.
Printing every solution twice.
Removing all recursion.
Sorting output only.
Why unmark a grid cell in word search?
Other paths may need to use it later.
To sort the board.
To make DFS iterative.
To avoid including headers.