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 recuse 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++ implementation –**

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 |
#include <bits/stdc++.h> using namespace std; #define M 3 #define N 3 // Function to check if (i, j) is valid matrix cordinate 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> 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); } // 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; } |

`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

**Time complexity** of above solution is exponential.

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

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

**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. Make above code memory efficient. (Hint – Pass vector by reference and use Backtracking)

2. Convert above solution to DP using memoization.

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

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

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

## Leave a Reply

Exercise 1 solution (pass by reference and backtrack): http://cpp.sh/72fh