Print all paths from top left to bottom right of MxN matrix

Previous
Next

In this post, we will see how to print all paths from top left to bottom right of MxN matrix.


Problem

We need to print all paths from top left to bottom right of MxN matrix. You can either move down or right.

Print matrix paths


Solution

You can solve this problem using recursion.

Recursion

  • We will pass row and column to track current row and column.
  • paths will contain elements which we are going to print.
  • Add current element to the path
    • paths.add(matrix[row][column]);
  • Go down by updating row to row+1
    • matrixPathHelper(list, paths, matrix,row+1,column);
  • Go right by updating column to column+1
    • matrixPathHelper(list, paths, matrix,row,column+1);
  • Once we are done, backtrack by removing last element from the list.
    • paths.remove(paths.size() – 1);
  • Base case 1:
    • Once we reach to last row, we can only go right, so iterate from column to matrix[0].length and add elements to paths.
  • Base case 2:
    • Once we reach to last column, we can only go down, so iterate from row to matrix.length and add elements to paths.

Here is complete java program to print all paths from top left to bottom right of MxN matrix.

Output

Paths:
[1, 4, 7, 8, 9]
[1, 4, 5, 8, 9]
[1, 4, 5, 6, 9]
[1, 2, 5, 8, 9]
[1, 2, 5, 6, 9]
[1, 2, 3, 6, 9]

Here is diagram to illustrate recursion.

Print Matrix paths recursion
Please open above image in a new tab.

That’s all about how to print all paths from top left to bottom right of MxN matrix

Previous
Next

Join Our News Letter – Stay Updated

Subscribe to Awesome Java Content.




Add Comment

Join Our News Letter - Stay Updated

Subscribe to Awesome Java Content.
You can like our facebook page Java2blog