Unique Paths III - Solution & Explanation

This approach uses a Depth-First Search (DFS) technique with backtracking to explore every possible path from the start to the end square. We first count all the empty squares and ensure that each path covers all these squares exactly once. Starting from the initial position, we recursively visit adjacent squares, marking them as visited to ensure they aren't visited again during the same path. If a path reaches the end square and has visited all empty squares, it's a valid path.

The solution uses DFS to explore all possible paths recursively. The dfs() function is defined to attempt moving in four directions from the current cell. We mark the current cell as visited by temporarily setting it to -2 and backtrack by restoring its value to 0, enabling alternative paths. We use a counter variable, remain, to track the number of unvisited non-obstacle squares. If we reach the target square after visiting all non-obstacle squares, it's counted as one unique path.

In this approach, we use dynamic programming to reduce the problem into smaller overlapping subproblems. With state compression, we leverage bitmasking to track visited squares in the grid efficiently. Each state is represented by a combination of the current cell and a bitmask that indicates which of the necessary cells (squares) have been covered. The problem then simplifies into finding paths to cover large subproblems using previously computed smaller subproblem solutions.

This method involves initializing a 2D DP table and iteratively computing the number of paths by considering smaller subsets of the grid using bitmask representation. Each cell represents the state of paths leading to it, which can be updated from adjacent cells. This method maximizes efficiency by avoiding repetitive computations, combining overlapping solutions with dynamic programming. Details are omitted due to space limitations.