Unique Paths III
Hard · Backtracking · Array · Backtracking · Bit Manipulation · Matrix
Problem
You are given an m x n grid where each square is one of:
- 1: the starting square (there is exactly one);
- 2: the ending square (there is exactly one);
- 0: an empty square you can walk over;
- -1: an obstacle you cannot enter.
Return the number of walks from the start to the end, moving up, down, left or right, that step on every non-obstacle square exactly once.
Examples
Input: grid = [[1,0,0],[0,0,2]] Output: 1
The only full walk goes down, right, up, right and down again.
Input: grid = [[1,0],[0,2]] Output: 0
Any walk to the end passes only one of the two empty squares.
Input: grid = [[1,-1],[0,2]] Output: 1
The only route goes down and then right.
Constraints
- m == len(grid), n == len(grid[i])
- 1 <= m, n <= 20
- 1 <= m · n <= 20
- -1 <= grid[i][j] <= 2
- Exactly one starting square and one ending square
Approaches
- Baseline: grow every path as a list — time O(3^k · k), space O(3^k · k) in the worst case
Follow-up
With a bitmask of the used squares, (square, mask) determines the number of ways to finish, so the count can be memoized: O(k² · 2^k) states and moves, which helps when many walks share the same remaining squares. See the use cases for the longest walk from start to end, and for covering everything with no fixed end.
Related problems
Start free on Cariara · Coding problems · System design studio
