BackTrackingProblem 17 of 19
Print all possible paths from top left to bottom right of a mXn matrix
Problem Statement
Given an m×n matrix, find and print all possible paths from the top-left cell (0,0) to the bottom-right cell (m-1,n-1). You can only move right or down at any point.
Example:
Input: matrix = [[1, 2, 3],
[4, 5, 6]]
Output:
Path 1: 1 -> 2 -> 3 -> 6
Path 2: 1 -> 2 -> 5 -> 6
Path 3: 1 -> 4 -> 5 -> 6
Explanation: All paths from (0,0) to (1,2) moving only right or down.
Approach 1: Brute Force (Simple Recursion)
Intuition
At each cell, we have two choices: move right or move down. Use recursion to explore both choices and collect paths that reach the destination.
Algorithm
- Start from (0, 0)
- At each cell, try moving right and down
- When destination reached, store the path
- Continue until all paths explored
java
import java.util.*;
class Solution {
public void findPaths(int[][] matrix, int row, int col,
List<Integer> path, List<List<Integer>> result) {
int m = matrix.length;
int n = matrix[0].length;
// Add current cell to path
path.add(matrix[row][col]);
// Reached destination
if (row == m - 1 && col == n - 1) {
result.add(new ArrayList<>(path));
path.remove(path.size() - 1);
return;
}
// Move right
if (col + 1 < n) {
findPaths(matrix, row, col + 1, path, result);
}
// Move down
if (row + 1 < m) {
findPaths(matrix, row + 1, col, path, result);
}
path.remove(path.size() - 1); // Backtrack
}
public List<List<Integer>> allPaths(int[][] matrix) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
findPaths(matrix, 0, 0, path, result);
return result;
}
}Complexity Analysis
- Time Complexity: O(2^(m+n)) - At each step, 2 choices
- Space Complexity: O(m+n) - Path length and recursion depth
Approach 2: With String Direction Path
Intuition
Instead of storing values, store the directions (R for right, D for down) to trace the path.
java
import java.util.*;
class Solution {
public void findPaths(int m, int n, int row, int col, String path,
List<String> result) {
// Reached destination
if (row == m - 1 && col == n - 1) {
result.add(path);
return;
}
// Move right
if (col + 1 < n) {
findPaths(m, n, row, col + 1, path + "R", result);
}
// Move down
if (row + 1 < m) {
findPaths(m, n, row + 1, col, path + "D", result);
}
}
public List<String> allPaths(int m, int n) {
List<String> result = new ArrayList<>();
findPaths(m, n, 0, 0, "", result);
return result;
}
}Complexity Analysis
- Time Complexity: O(2^(m+n))
- Space Complexity: O(m+n)
Approach 3: With 4 Directions (All Movements)
Intuition
If we allow all 4 directions, we need to track visited cells to avoid cycles.
java
import java.util.*;
class Solution {
private int[] dr = {-1, 0, 1, 0};
private int[] dc = {0, 1, 0, -1};
private char[] dir = {'U', 'R', 'D', 'L'};
public void findPaths(int m, int n, int row, int col, String path,
boolean[][] visited, List<String> result) {
// Reached destination
if (row == m - 1 && col == n - 1) {
result.add(path);
return;
}
visited[row][col] = true;
// Try all 4 directions
for (int i = 0; i < 4; i++) {
int newRow = row + dr[i];
int newCol = col + dc[i];
if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n &&
!visited[newRow][newCol]) {
findPaths(m, n, newRow, newCol, path + dir[i], visited, result);
}
}
visited[row][col] = false; // Backtrack
}
public List<String> allPaths(int m, int n) {
List<String> result = new ArrayList<>();
boolean[][] visited = new boolean[m][n];
findPaths(m, n, 0, 0, "", visited, result);
return result;
}
}Complexity Analysis
- Time Complexity: O(4^(m×n)) for 4 directions
- Space Complexity: O(m×n) - Visited array
Count of Paths (DP Approach)
For just counting paths (right and down only):
Key Takeaways
- Two Choices: Right or down at each cell
- Path Count: C(m+n-2, m-1) for right/down only
- 4 Directions: Need visited array to avoid cycles
- Backtracking: Essential for exploring all paths
- LeetCode #62: Unique Paths (counting version)
- LeetCode #63: Unique Paths II (with obstacles)