Unique Paths III - Video Solutions

Problem Overview: You are given a grid containing a start cell, an end cell, empty squares, and obstacles. Count how many paths move from start to end while visiting every non-obstacle cell exactly once. Movement is allowed in four directions, and you cannot revisit a cell.

Approach 1: Backtracking with Depth-First Search (O(3^k) time, O(k) space)

This problem naturally maps to backtracking over a matrix. First scan the grid to locate the start position and count how many cells must be visited (all empty cells plus the start). From the start, run DFS and recursively explore four directions. Mark the current cell as visited (often by temporarily modifying the grid), decrement the remaining cell counter, and continue exploring neighbors that are inside bounds and not obstacles. When you reach the end cell, the path is valid only if every required cell has been visited.

The key insight: each recursive call represents a partial path. Backtracking restores the cell state after exploring a branch so other paths can reuse it. Since you can move to at most three new cells at each step (excluding the previous cell), the search space is roughly O(3^k), where k is the number of walkable cells. Space complexity is O(k) due to the recursion stack. This approach is straightforward and performs well because grid sizes are small.

Approach 2: Dynamic Programming with State Compression (O((m*n) * 2^k) time, O((m*n) * 2^k) space)

This approach models the problem as visiting cells with a bitmask representing the visited state. Each walkable cell receives an index. A DP state looks like dp[r][c][mask], meaning the number of ways to reach cell (r,c) with the set of visited cells encoded in mask. Transition by moving to adjacent cells and updating the bitmask using bit manipulation. The final answer counts states where the end cell is reached with every required bit set.

The insight is that path validity depends only on the current position and which cells were already visited. Encoding visited cells as a bitmask avoids recomputation of identical states encountered via different paths. With k walkable cells, there are at most 2^k masks and m*n positions, producing O((m*n) * 2^k) states. Although heavier in memory, this method demonstrates how Hamiltonian path-style grid problems can be solved using state compression.

Recommended for interviews: Backtracking with DFS is the expected solution. It directly models the constraint of visiting every square exactly once and is easier to implement under pressure. Interviewers often look for clean recursion, correct base conditions, and proper state restoration. State compression DP is an advanced optimization idea and useful when discussing alternative formulations or demonstrating strong understanding of bitmask DP.