# Find all paths from first cell to last cell of a matrix

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.

## Java

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.

(1 votes, average: 5.00 out of 5)

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 🙂