[[0, 0], [1, 0], [2, 0], [2, 1], [2, 2]] ] Explanation: There is one obstacle in the middle of the 3x3 grid above. There are two ways to reach the bottom-right corner: 1. Right -> Right -> Down -> Down 2. Down -> Down -> Right -> Right

Example 2:

Input:
obstacleGrid =[[0,1],[0,0]]
Output:
 [ 
	[[0, 0], [1, 0], [1, 1]]
 ]

Note: m and n will be at most 100.

Follow-up

What if you need to return any valid path? (Answered inside Method 1.)

Solution

Method 1 - Backtracking Enumeration (All Paths)

Intuition

Every valid path from top-left to bottom-right using only Right and Down steps (and avoiding obstacles) can be represented as a sequence of at most (m + n - 2) decisions. A depth-first traversal that tries both allowed directions from each cell will enumerate all such paths. Because movement is monotonic (never up/left), no cycles occur, so we do not need a visited matrix—each path prefix is unique in the search tree.

Approach

Start DFS from (0, 0); maintain a current path list.
If current cell is out of bounds or an obstacle (1), return.
Append current cell to path.
If destination reached, copy path to results.
Recurse (Down, then Right or any fixed order) and backtrack by removing the cell.

Code

[{"language":"Java","code":"public class Solution {\n\tpublic List<List<int[]>> enumerateAllPaths(int[][] grid) {\n\t\tList<List<int[]>> res = new ArrayList<>();\n\t\tint m = grid.length, n = grid[0].length;\n\t\tif (grid[0][0] == 1 || grid[m-1][n-1] == 1) return res;\n\t\tdfs(grid, 0, 0, new ArrayList<>(), res);\n\t\treturn res;\n\t}\n\n\tprivate void dfs(int[][] g, int r, int c, List<int[]> cur, List<List<int[]>> res) {\n\t\tint m = g.length, n = g[0].length;\n\t\tif (r < 0 || c < 0 || r >= m || c >= n || g[r][c] == 1) return;\n\t\tcur.add(new int[]{r,c});\n\t\tif (r == m - 1 && c == n - 1) {\n\t\t\tres.add(new ArrayList<>(cur));\n\t\t} else {\n\t\t\tdfs(g, r + 1, c, cur, res); // Down\n\t\t\tdfs(g, r, c + 1, cur, res); // Right\n\t\t}\n\t\tcur.remove(cur.size()-1);\n\t}\n}","lang":"java","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span

Related Tags