Problem

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return all possible unique paths that the robot can take to reach the bottom-right corner.

Examples

Example 1:

1
2
3
4
5
6

Input : m = 2, n = 2
Output : [ 
	[[0, 0], [0,1], [1,1]],
	[[0, 0], [1, 0], [1,1]]

2 possible routes : (0, 0) -> (0, 1) -> (1, 1)

Follow up

Imagine certain squares are “off limits”, such that the robot can not step on them. Design an algorithm to get all possible paths for the robot.

Refer Unique Paths in Grid 2-2 - Get all paths moving right or down with obstacles

Solution

Method 1 - Backtracking

We solved the similar question - Unique Paths in Grid 1 - Count all paths moving right or down, where we had to find the count of number of paths. Here we have to print the paths.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

public class Solution {

	public List < List<int[] >> findAllPaths(int m, int n) {
		List <List<int[]>> paths = new ArrayList<>();
		List <int[]> currentPath = new ArrayList<>();
		currentPath.add(new int[] {
			0, 0
		});
		backtrack(m, n, 0, 0, currentPath, paths);
		return paths;
	}

	private void backtrack(int m, int n, int row, int col, List <int[]> currentPath, List <List<int[]>> paths) {
		if (row == m - 1 && col == n - 1) {
			paths.add(new ArrayList<>(currentPath)); // Add a copy of the currentPath
			return;
		}

		// Move Down
		if (row < m - 1) {
			currentPath.add(new int[] {
				row + 1, col
			}); // Move down
			backtrack(m, n, row + 1, col, currentPath, paths);
			currentPath.remove(currentPath.size() - 1); // Backtrack
		}

		// Move Right
		if (col < n - 1) {
			currentPath.add(new int[] {
				row, col + 1
			}); // Move right
			backtrack(m, n, row, col + 1, currentPath, paths);
			currentPath.remove(currentPath.size() - 1); // Backtrack
		}
	}

	public static void main(String[] args) {
		Solution solution = new Solution();
		List < List<int[] >> paths = solution.findAllPaths(2, 3);

		// Print all paths
		for (List < int[] > path: paths) {
			System.out.print("[ ");

			for (int[] step: path) {
				System.out.print("[" + step[0] + "," + step[1] + "] ");
			}

			System.out.println("]");
		}
	}
}

Complexity

  • ⏰ Time complexity: O(2 ^ (m+n))
  • 🧺 Space complexity: O(m + n) for recursive stack