Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Print All Paths from Top left to bottom right in Two Dimensional Array

Objec­tive: Print all the paths from left top cor­ner to right bot­tom cor­ner in two dimen­sional array.

Input: Two Dimen­sional array

Out­put: Print all the paths.

Note: At the End of the arti­cle you will know what needs to be included if you want to print the diag­o­nal paths as well.

Exam­ple:

Print All Paths - Example

Print All Paths — Example

Approach:

As we need to explore all the paths from top left cor­ner to bot­tom right cor­ner, we will either travel down OR travel right. so every time either we increase the row or column.

  • Recur­sion is the key here.
  • Take the rows count and col­umn counts say row­Count and col­Count respectively
  • Take cur­ren­tRow =0 and cur­rent­Col­umn =0 and path =””
  • Call printAll(currentRow, currentcolumn,path)
  • Add array[0][0] to the path.
  • Call recur­sively printAll(currentRow+1, currentcolumn,path)
  • Call recur­sively printAll(currentRow, currentcolumn+1,path)
  • Base Case 1: when cur­ren­tRow = rowCount-1(because array index starts with 0) , print the rest of the columns, return
  • Base Case 2: when cur­rent­col­umn = colCount-1(because array index starts with 0) , print the rest of the rows, return

Like always you need to trust Recur­sion to get you the cor­rect result. 🙂

Recursion Tree -Print All Paths

Recur­sion Tree –Print All Paths

Com­plete Code:


Out­put:

-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

Note: printAll(currentRow+1,currentColumn+1,path); Add this line when you want to print diag­o­nal paths as well (see code)

You may also like...

  • deen john

    this code is not pro­duc­ing the cor­rect out­put. please check. i am get­ting :-1–4-5–6

    –1–2-5–6

    –1–2-3–6

    –1–2-6

    –1–5-6

    • tuto­ri­al­hori­zon

      Is it nxn matrix u r providing ?

      • deen john

        the code is cor­rect but it’s for ” Print All Paths from Top left to bot­tom right in Two Dimen­sional Array includ­ing Diag­o­nal” not “Print All Paths from Top left to bot­tom right in Two Dimen­sional Array”. you haven’t com­ment the line– printAll(currentRow + 1, cur­rent­Col­umn + 1, path);

      • deen john

        I like your web­site for the detailed easy answers and it’s a big help. I have a small request too– Could you please add tuto­ri­als for Graph based algorithms/Datastructures problems .

  • deen john

    there is some prob­lem with your code. it’s not pro­duc­ing cor­rect result