Medium · Grid Backtracking
Understand → Visualise → Practice.
Count simple paths from the top-left to bottom-right through zero cells, moving orthogonally without revisiting a cell.
Count simple paths with DFS: mark a cell as visited while exploring from it, and unmark it when you return so other paths may use it.
Out of bounds, a wall (1) or already on the current path: 0 paths.
The bottom-right cell counts as 1 path.
Mark the cell, add the counts from all four neighbours, then unmark it.
Exponential in the number of open cells in the worst case; O(cells) recursion depth.
Leaving cells marked after returning blocks valid paths that use them differently.
Read the full guide first: Recursion and Backtracking.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.