Solution: Unique Paths III

Explore how to apply backtracking to find every unique path in a grid from start to end, visiting all empty squares exactly once without crossing obstacles. Understand the recursive process of path exploration, marking visited cells, and backtracking steps. By the end, you'll be able to implement and analyze the solution's time and space complexities for this combinatorial problem.

We'll cover the following...

Statement
Solution
- Time complexity
- Space complexity

Statement

You are given a $m \times n$ integer array, grid, where each cell, grid[i][j], can have one of the following values:

1 indicates the starting point. There is exactly one such square.
2 marks the ending point. There is exactly one such square.
0 represents empty squares that can be walked over.
-1 represents obstacles that cannot be crossed.

Your task is to return the total number of unique four-directional paths from the starting square (1) to the ending square (2), such that every empty square is visited exactly once during the walk.

Constraints:

$m$ $==$ grid.length
$n$ $==$ grid[i].length
$1 \leq$ ...