Given a M x N matrix, find all paths from first cell to last cell. We can only move down or to the right from the current cell.

For example,

**Input: **

{ 1 2 3 }

{ 4 5 6 }

{ 7 8 9 }

**Output: **

1 – 2 – 3 – 6 – 9

1 – 2 – 5 – 6 – 9

1 – 2 – 5 – 8 – 9

1 – 4 – 5 – 6 – 9

1 – 4 – 5 – 8 – 9

1 – 4 – 7 – 8 – 9

We can easily solve this problem using recursion. The idea is to start from the top-left cell of the matrix and recurse for next node (immediate right or immediate bottom cell) and keep on doing that for every visited cell till destination is reached. We maintain a path array to store the nodes in current path and update the path array (include current node in it) whenever we visit any cell. Whenever destination (bottom-right corner) is reached, we print the path array.

## C++

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 54 55 56 57 58 59 60 61 62 63 64 |
#include <iostream> #include <vector> using namespace std; #define M 3 #define N 3 // Function to check if (i, j) is valid matrix coordinate bool isvalid(int i, int j) { return (i >= 0 && i < M && j >= 0 && j < N); } // Function to print the route taken void printPath(vector<int> const &path, int last) { for (int i : path) cout << i << " - "; cout << last << endl; } void findPaths(int mat[][N], vector<int> &path, int i, int j) { // if we have reached the last cell, print the route if (i == M - 1 && j == N - 1) { printPath(path, mat[i][j]); return; } // include current cell in path path.push_back(mat[i][j]); // move right if (isvalid(i, j + 1)) findPaths(mat, path, i, j + 1); // move down if (isvalid(i + 1, j)) findPaths(mat, path, i + 1, j); // remove current cell from the path path.pop_back(); } // main function int main() { int mat[M][N] = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }; vector<int> path; // start from (0, 0) cell int x = 0, y = 0; findPaths(mat, path, x, y); return 0; } |

## Java

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 54 55 56 57 58 59 60 61 |
import java.util.ArrayList; import java.util.List; class Util { // Function to print the route taken public static void printPath(List<Integer> path, int last) { for (int i : path) { System.out.print(i + " - "); } System.out.println(last); } public static void findPaths(int[][] mat, List<Integer> path, int i, int j) { int M = mat.length; int N = mat[0].length; // if we have reached the last cell, print the route if (i == M - 1 && j == N - 1) { printPath(path, mat[i][j]); return; } // include current cell in path path.add(mat[i][j]); // move right if ((i >= 0 && i < M && j + 1 >= 0 && j + 1 < N)) { findPaths(mat, path, i, j + 1); } // move down if ((i + 1 >= 0 && i + 1 < M && j >= 0 && j < N)) { findPaths(mat, path, i + 1, j); } // remove current cell from path path.remove(path.size() - 1); } public static void main(String[] args) { int[][] mat = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }; List<Integer> path = new ArrayList<>(); // start from (0, 0) cell int x = 0, y = 0; findPaths(mat, path, x, y); } } |

`Output:`

1 – 2 – 3 – 6 – 9

1 – 2 – 5 – 6 – 9

1 – 2 – 5 – 8 – 9

1 – 4 – 5 – 6 – 9

1 – 4 – 5 – 8 – 9

1 – 4 – 7 – 8 – 9

The time complexity of above solution is exponential.

T(M, N) = T(M, N-1) + T(M-1, N) // for two recursive calls

T(M, 1) = M, T(1, N) = N, T(1, 1) = 1

The auxiliary space used by the program is O(M + N).

If we carefully analyze the solution, we can see the problem has *overlapping sub-problems*. So it can be solved using Dynamic Programming and time complexity can be reduced drastically (space complexity will also increase drastically).

**Exercise:**

1. Convert above solution to DP using memoization.

2. Convert above code to C language using array to store path information.

**Thanks for reading.**

Please use our online compiler to post code in comments. To contribute, get in touch with us.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

Nice solution.

There’s a mistake in the C++ implementation, cells are added to the path but never eventually removed.

Thanks for sharing your concerns. Since the vector was passed by value, this was not required. But we have made the code memory efficient by passing the vector by reference and backtracking is used.