Unique Paths III

Explanation & Solution

Description

You are given an m x n integer array grid where:

1 represents the starting square. There is exactly one starting square.
2 represents the ending square. There is exactly one ending square.
0 represents empty squares we can walk over.
-1 represents obstacles that we cannot walk over.

Return the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once.

Examples

Example 1

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

Output: 2

Explanation: There are two paths that visit every non-obstacle cell exactly once: right→right→right→down→down and right→right→down→down→right (adapting direction as needed).

Example 2

Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,0,2]]

Output: 4

Explanation: There are four valid Hamiltonian paths from the start to the end covering all empty cells.

Example 3

Input: grid = [[0,1],[2,0]]

Output: 0

Explanation: No path from start to end can visit all 4 non-obstacle cells exactly once.

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 20
1 <= m * n <= 20
-1 <= grid[i][j] <= 2
There is exactly one 1 and one 2 in grid

Approach

Backtracking pattern

1. Count Non-Obstacle Cells

Scan the grid to find the starting position and count all cells that are not obstacles (!= -1)
This count tells us how many cells a valid path must visit

2. DFS with Remaining Counter

Start DFS from the starting cell with remaining = empty (total non-obstacle cells)
At each step, decrement remaining to track how many cells still need to be visited

3. Check the Ending Condition

When we reach the ending cell (grid[r][c] === 2), check if remaining === 1 (only the end cell is left to count)
If so, this is a valid Hamiltonian path — increment result

4. Backtrack on the Grid

Save the cell's value, mark it as an obstacle (-1) to prevent revisiting
Explore all four directions
Restore the cell's original value after exploration

Key Insight

This is a Hamiltonian path problem — NP-hard in general, but feasible here because the grid is small (≤ 20 cells). Backtracking with in-place marking is the natural approach.

Time

**O(4^(m×n))** worst case, but aggressive pruning makes it practical for small grids

Space

O(m × n) for the recursion stack

Visualization

Input:

Backtracking Search3×4 grid

output—

Press play to start backtracking search

CurrentQueuedVisitedSource

2 steps

Solution Code

Combination Sum II