Print All Possible Paths From Top Left Corner To Bottom Right Corner Of A 2-D Matrix

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
16 upvotes
Asked in companies
HCL TechnologiesAmazonOracle

Problem statement

You are given an ‘M*N’ Matrix, You need to print all possible paths from its top left corner to the bottom right corner if given that you can either move right i.e from (i,j) to (i,j+1) or down i.e from (i, j) to (i+1, j).

For Example : 
1 2 3
4 5 6

For the above 2*3 matrix , possible paths are (1 2 3 6) , (1 2 5 6) , (1 4 5 6).
Note : 
You can return the paths in any order.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains two space-separated integers, ‘M’ and ‘N’ denoting the number of rows and columns of the given matrix.

Each of the following ‘M’ lines contains N space-separated numbers.
Output Format : 
Print all the paths in a new line.
Note : 
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints : 
1 <= M, N <= 10

Time Limit: 1 sec
Sample Input 1 :
2 2
1 2 
3 4
Sample Output 1 :
1 3 4
1 2 4
Explanation Of Sample Input 1 :
All the possible paths on moving right and down are (1 3 4) and (1 2 4).
Sample Input 2 :
3 2
5 10 
15 20
25 30
Sample Output 2 :
5 15 25 30
5 15 20 30
5 10 20 30
Hint

 Can we use recursion to generate all the paths?

Approaches (1)
Recursion

The basic idea to solve this problem is to use recursion. Recursively call function   for next row ( row+1,col ) and next column ( row, col+1 ). If the row is equal to M-1 or the column is equal to N-1, then recursion is stopped.

 

Algorithm:

  • Take an array or vector ‘path’, which will store the path we have to print.
  • Start from the index (row, col) = (0,0).
  • Add mat(row, col) to  ‘path.’
  • Recursively call for next row  ( row+1, col ) and next column ( row, col+1 ).
  • If  ‘row’ == ‘M-1’, it means we are at the last row and can go right only. Iterate from ( row, col) to ( row, N-1)  and add elements to ‘path.’
  • Similarly, If ‘col’==’N-1’, it means we are at the last column and can go down only. Iterate from  (row, col) to ( M-1, col) and add elements to the ‘path.’

Let us understand the above approach with the help of a recursion tree for the matrix given below

1 2 3

4 5 6

            

           Output: 1 4 5 6

                        1 2 5 6

                        1 2 3 6

Time Complexity

 

O(2^(M+N)), where M is the number of rows and N is the number of columns.

 

The minimum length from root to a leaf node in the recursion tree is min(M, N) and the maximum length is M+N. Therefore the total number of nodes is between 2^min(M, N) and 2^(M+N). Hence time complexity is O(2^(M+N)).

Space Complexity

O(M+N).

 

Extra space used to store the path.

Code Solution
(100% EXP penalty)
Print All Possible Paths From Top Left Corner To Bottom Right Corner Of A 2-D Matrix
Full screen
Console