Unique Paths III

01 · Question

You are given an m x n integer array grid where grid[i][j] could be:

1 representing the starting square. There is exactly one starting square.
2 representing the ending square. There is exactly one ending square.
0 representing empty squares we can walk over.
-1 representing obstacles that we cannot walk over.

Return the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once.

02 · Analysis

Track the current cell and how many non-obstacle cells remain. Entering a cell marks it unavailable only for the current branch; restore it when returning. Reaching the destination contributes one only if all required cells were visited. For F traversable cells, a loose upper bound is O(4^F) search time, with O(F) recursion/visited space. Memoizing only the cell loses which cells are already used and is incorrect.

03 · Solution

Reference solution

1def uniquePathsIII(grid: List[List[int]]) -> int:
2    R, C = len(grid), len(grid[0])
3    empty_count = 0
4    start_r = start_c = 0
5
6    for r in range(R):
7        for c in range(C):
8            if grid[r][c] == 0:
9                empty_count += 1
10            elif grid[r][c] == 1:
11                start_r, start_c = r, c
12
13    res = 0
14
15    def dfs(r, c, empty_visited):
16        nonlocal res
17        if r < 0 or r >= R or c < 0 or c >= C or grid[r][c] == -1:
18            return
19
20        if grid[r][c] == 2:
21            if empty_visited == empty_count + 1:
22                res += 1
23            return
24
25        # Mark as visited
26        temp = grid[r][c]
27        grid[r][c] = -1
28
29        dfs(r + 1, c, empty_visited + 1)
30        dfs(r - 1, c, empty_visited + 1)
31        dfs(r, c + 1, empty_visited + 1)
32        dfs(r, c - 1, empty_visited + 1)
33
34        # Backtrack
35        grid[r][c] = temp
36
37    dfs(start_r, start_c, 0)
38    return res

Combination Sum II

Subsets