Last Updated: 18 Feb, 2021

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

Moderate

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 Approach

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

Solve now