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.

C++

Download   Run Code

Java

Download   Run Code

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.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Vivek Pal
Guest

Nice solution.

yndi
Guest

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