Course4all

Unique Paths III

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Backtracking.

Unique Paths III

The Grid Coverage Problem

Find the number of paths from the starting square to the ending square that walk over every non-obstacle square exactly once.

Backtracking with Path Counting

  1. Count the total number of empty squares (NN).
  2. DFS from the start, marking cells as visited (-1).
  3. If we reach the end and our current path length equals N+1N+1 (including the target), we found a valid path.
Find the number of paths in a grid that visit every empty square exactly once. Includes visual grid-coverage trace.
Hard

Examples

Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
Approach 1

Level I: Backtracking (DFS)

Intuition

Try all possible paths from start to end, counting steps taken.
Iterate through the grid to find the start and count empty cells. DFS in 4 directions. If we reach '2' and steps == totalEmpty, increment count.
⏱ O(3^{M * N})💾 O(M * N)

Detailed Dry Run

Trace for 1x3: [1, 0, 2] 1. Start at (0,0), empty=2. 2. Move to (0,1), steps=1. Mark visited. 3. Move to (0,2), steps=2. Target reached! Count++
java
class Solution {
    int res = 0, empty = 1, startX, startY;
    public int uniquePathsIII(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0) empty++;
                else if (grid[i][j] == 1) {
                    startX = i; startY = j;
                }
            }
        }
        dfs(grid, startX, startY, 0);
        return res;
    }
    public void dfs(int[][] grid, int x, int y, int count) {
        if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == -1) return;
        if (grid[x][y] == 2) {
            if (count == empty) res++;
            return;
        }
        grid[x][y] = -1;
        dfs(grid, x + 1, y, count + 1);
        dfs(grid, x - 1, y, count + 1);
        dfs(grid, x, y + 1, count + 1);
        dfs(grid, x, y - 1, count + 1);
        grid[x][y] = 0;
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionBeautiful Arrangement
Next Question →Hamiltonian Path