Unique Paths III

Unique Paths III is a classic backtracking problem. It looks like a grid-walk question, but the real lesson is the mark / recurse / un-mark rhythm that every backtracking solution shares.

The slow way first

There is no clever shortcut here: we genuinely have to try paths. The naive worry is that we might revisit squares or wander forever. The fix is to track which squares are on the current path and refuse to step on one twice. That turns an infinite walk into a finite tree of choices we can search exhaustively.

The question to ask: how do I try a square, explore everything that follows, and then cleanly undo my choice so I can try the next one? That is exactly what backtracking gives us.

The idea: count, then DFS with un-marking

First count how many squares we must cover (every 0, plus the start). Then run a depth-first search from the start. At each square we mark it visited, recurse into its unvisited neighbours, and then un-mark it on the way out so other paths can use it. A path scores 1 only when we land on the end square having covered all squares.

The key insight: the un-mark step is what makes one DFS explore many paths instead of just one. Without it, a square used by an early dead-end would stay blocked forever.

Walk through it

Step through the animation. The square we are standing on glows; squares already on the path turn visited. We snake through all 9 squares and finish on the end square 2. When a branch hits an already-visited neighbour it is blocked and backtracks. Landing on the end with every square covered counts as one path.

Pseudocode

empty = count of 0-squares + 1 (the start)
find the start square
 
dfs(r, c, remaining):
    mark (r, c) visited
    remaining -= 1
    if (r, c) is the end square:
        return 1 if remaining == 0 else 0   # only valid if all covered
    total = 0
    for each in-bounds neighbour (nr, nc):
        if (nr, nc) is not visited / not an obstacle:
            total += dfs(nr, nc, remaining)
    un-mark (r, c)                           # backtrack
    return total
 
answer = dfs(start, empty)

The Python solution

def unique_paths(grid):
    empty = sum(row.count(0) for row in grid) + 1
    start = find(grid, 1)
 
    def dfs(r, c, remaining):
        grid[r][c] = -1            # mark visited
        remaining -= 1
        if grid_was_end(r, c):
            return 1 if remaining == 0 else 0
        total = 0
        for nr, nc in neighbours(r, c):
            if grid[nr][nc] != -1:
                total += dfs(nr, nc, remaining)
        grid[r][c] = 0             # un-mark (backtrack)
        return total
 
    return dfs(*start, empty)

• empty is the number of squares we must cover: every 0 plus the start square itself.
• start is the (row, col) of the 1 square; the search begins there.
• Line 6 marks the current square by overwriting it with -1 (the same value as an obstacle), so neighbours treat it as off-limits.
• Line 9 is the scoring line: we only return 1 when we are on the end square and remaining == 0, meaning every square has been covered.
• The loop tries each neighbour that is not an obstacle or already visited, summing the paths each yields.
• Line 14 is the heart of backtracking — we un-mark the square back to 0 before returning, freeing it for other paths.

Complexity

The branching factor is at most 4 (the four directions), and the grid has R·C squares, so the worst case is exponential. The visited-marking prunes hard in practice, but the upper bound stays exponential — typical for exhaustive backtracking. Space is O(R·C) for the recursion depth.

When this pattern shows up

Practice