Unique Paths III
Understanding the Problem
This looks like a standard pathfinding problem: find a path from the start cell (value 1) to the end cell (value 2). The added constraint is what makes it different. The path must visit every walkable cell exactly once. It cannot skip any empty square, and it cannot revisit one.
That constraint turns this into a problem of counting Hamiltonian paths on a grid graph, restricted to a specific start and end. Counting Hamiltonian paths is NP-hard in general, but the constraint m * n <= 20 tells us an exponential solution is acceptable here.
The plan is to explore all possible paths from start to end and count only the ones that visit every non-obstacle cell. With at most 20 non-obstacle cells, enumerating all possibilities with backtracking finishes quickly.
Key Constraints:
1 <= m * n <= 20→ The grid holds at most 20 cells. An exponential search over paths is feasible at this size, and there is no polynomial algorithm for the general problem.-1 <= grid[i][j] <= 2→ Four cell types. We preprocess the grid once to locate the start, the end, and the count of walkable cells.
Approach 1: Backtracking (DFS)
Intuition
Explore every possible path from start to end with depth-first search. At each cell, try moving in all four directions. Mark a cell as visited when stepping onto it and unmark it when backtracking, which enumerates all paths without revisiting cells.
To decide when a path counts, precompute the total number of non-obstacle cells (the start and end cells included). As the search walks, track how many cells it has visited. When it reaches the end cell, compare that count to the total. If they match, the path visited every walkable cell exactly once, so it is a valid Hamiltonian path.
The grid holds at most 20 cells. The branching factor is at most 4, the depth is at most 20, and the no-revisit rule prunes the search tree heavily, so this runs quickly at this input size.
Algorithm
- Scan the grid to find the starting cell position, the ending cell position, and count the total number of non-obstacle cells (cells with values 0, 1, or 2).
- Start DFS from the starting cell with a visited count of 1 (we have visited the start).
- At each cell, try all four directions (up, down, left, right).
- For each neighbor, check if it is within bounds, not an obstacle, and not already visited.
- Mark the neighbor as visited (set it to -1), recurse with visited count + 1, then unmark it (restore original value).
- If the current cell is the ending cell and the visited count equals the total non-obstacle cells, increment the result count.
- Return the total count after the DFS completes.
Example Walkthrough
Code
- Time Complexity: O(4^(mn)). From each cell the search branches into up to 4 directions, and a path can be up to mn cells long. The no-revisit rule prunes most branches, and with m*n <= 20 the search stays small.
- Space Complexity: O(m*n). The recursion stack goes as deep as the number of non-obstacle cells along the current path. Visited tracking modifies the grid in place, so no extra data structure is needed beyond the call stack.
The backtracking approach explores the same subproblems more than once. When two different paths reach the same cell having visited the same set of cells, the remaining work is identical, yet backtracking redoes the entire subtree. The next approach caches the result for each (current cell, visited set) pair.
Approach 2: Bitmask Dynamic Programming
Intuition
Different paths that arrive at the same cell with the same set of visited cells produce the same number of valid completions. Caching that result avoids re-exploring identical subtrees.
To cache it, the visited set has to become a compact, hashable key. Assign each non-obstacle cell an index from 0 to k-1 (where k is the total number of walkable cells), and represent the set of visited cells as a bitmask: an integer where bit i is set if cell i has been visited. The state becomes (current cell index, bitmask of visited cells), and its value is the number of ways to reach the end cell while visiting every remaining unvisited cell.
With at most 20 cells, the bitmask has at most 2^20 = 1,048,576 values, and there are at most 20 cells, so the state space is bounded by 20 * 2^20, around 20 million. That is feasible, and most of those states are never reached because a cell can only hold valid masks that include its own bit.
Memoizing on (cell, mask) is sound because the number of valid completions from a state depends only on the current cell and the set of already-visited cells, not on the order in which they were visited. The remaining choices, which cells are still reachable and unvisited, are fully determined by the mask. Two paths that arrive at cell X having visited the set {A, B, C} therefore have an identical count of ways to finish, so caching one and reusing it for the other is exact.
Algorithm
- Scan the grid to assign an index (0 to k-1) to each non-obstacle cell. Record the start index, end index, and adjacency between cells.
- Build the full bitmask where all cells are visited:
fullMask = (1 << k) - 1. - Use memoized DFS (or bottom-up DP) with state
(cellIndex, visitedMask). - Base case: if
cellIndexis the end cell andvisitedMask == fullMask, return 1. IfcellIndexis the end cell but not all cells are visited, return 0. - Transition: for each neighbor of the current cell that is not yet in
visitedMask, add the bit for the neighbor to the mask and recurse. - The answer is
dp(startIndex, 1 << startIndex).
Example Walkthrough
Code
- Time Complexity: O(k 2^k). There are k 2^k states (current cell index times the visited mask). Memoization computes each state once, and each computation iterates over at most 4 grid neighbors, a constant factor.
- Space Complexity: O(k * 2^k). The memoization table stores one value per state, which dominates the O(k) recursion stack.