Print all possible paths from top left to bottom right of matrix
The problem entails generating and printing all possible paths from the top-left corner to the bottom-right corner of a matrix. These paths can only move downwards or to the right. The task is to display all such paths in the given matrix.

Problem Statement
Given a matrix of characters, we need to find and print all possible paths from the top-left corner to the bottom-right corner of the matrix. The paths can only move in the downward and rightward directions.
Example
Consider the following matrix:
A B C D
E F G H
I J K L
M N O P
Q R S T
The possible paths from the top-left corner (A) to the bottom-right corner (T) are as follows:
- A E I M Q R S T
- A E I M N R S T
- A E I M N O S T
- A E I M N O P T
- A E I J N R S T
- A E I J N O S T
- A E I J N O P T
- A E I J K O S T
- A E I J K O P T
- A E I J K L P T
- A E F J N R S T
- A E F J N O S T
- A E F J N O P T
- A E F J K O S T
- A E F J K O P T
- A E F J K L P T
- A E F G K O S T
- A E F G K O P T
- A E F G K L P T
- A E F G H L P T
- A B F J N R S T
- A B F J N O S T
- A B F J N O P T
- A B F J K O S T
- A B F J K O P T
- A B F J K L P T
- A B F G K O S T
- A B F G K O P T
- A B F G K L P T
- A B F G H L P T
- A B C G K O S T
- A B C G K O P T
- A B C G K L P T
- A B C D H L P T
Idea to Solve
To solve this problem, we can use a recursive approach. At each step, we have two options: move downward or move to the right. We recursively explore both options while keeping track of the path we have taken so far.
Pseudocode
Here's the pseudocode to solve the problem:
function showPaths(matrix, result, row, col, count, k):
if row >= R or col >= C:
return
result[count] = matrix[row][col]
showPaths(matrix, result, row+1, col, count+1, k)
showPaths(matrix, result, row, col+1, count+1, k)
if count + 1 == k:
print result
function main():
define matrix
define result array
showPaths(matrix, result, 0, 0, 0, R+C-1)
main()
Algorithm Explanation
- At each step, place the character at the current cell into the
result
array. - Recursively explore the downward and rightward paths from the current cell, increasing the
count
by 1. - If the count becomes equal to the total length of the path (sum of rows and columns - 1), print the
result
array. - The recursion continues until either the row index or the column index goes beyond the matrix boundaries.
Code Solution
//C Program
//Print all possible paths from top left to bottom right of matrix
#include<stdio.h>
#define R 5
#define C 4
//Display of all path of top to bottom and left to right
void show_path(char mat[R][C],char result[],int row ,int col,int count,int k)
{
if(row >= R || col >= C)
{
return;
}
result[count]=mat[row][col];
//recursive execute method with new parameters
show_path(mat,result,row+1,col,count+1,k);
show_path(mat,result,row,col+1,count+1,k);
if(count+1==k)
{
//Display the result value
for (int i = 0; i <k; ++i)
{
printf("%3c",result[i]);
}
printf("\n");
}
}
int main()
{
char mat[R][C] = {
{'A', 'B', 'C', 'D'},
{'E', 'F', 'G', 'H'},
{'I', 'J', 'K', 'L'},
{'M', 'N', 'O', 'P'},
{'Q', 'R', 'S', 'T'},
};
//Auxiliary memory which are storing path result
char result[R+C-1];
show_path(mat,result,0,0,0,R+C-1);
return 0;
}
Output
A E I M Q R S T
A E I M N R S T
A E I M N O S T
A E I M N O P T
A E I J N R S T
A E I J N O S T
A E I J N O P T
A E I J K O S T
A E I J K O P T
A E I J K L P T
A E F J N R S T
A E F J N O S T
A E F J N O P T
A E F J K O S T
A E F J K O P T
A E F J K L P T
A E F G K O S T
A E F G K O P T
A E F G K L P T
A E F G H L P T
A B F J N R S T
A B F J N O S T
A B F J N O P T
A B F J K O S T
A B F J K O P T
A B F J K L P T
A B F G K O S T
A B F G K O P T
A B F G K L P T
A B F G H L P T
A B C G K O S T
A B C G K O P T
A B C G K L P T
A B C G H L P T
A B C D H L P T
/*
C++ Program
Print all possible paths from top left to bottom right of matrix
*/
#include<iostream>
#define R 5
#define C 4
using namespace std;
class MyMatrix {
public:
int rows;
int cols;
//Display of all path of top to bottom and left to right
void show_path(char matrix[][C], char result[], int row, int col, int count, int k) {
if (row >= R || col >= C) {
return;
}
result[count] = matrix[row][col];
//recursive execute method with new parameters
this->show_path(matrix, result, row + 1, col, count + 1, k);
this->show_path(matrix, result, row, col + 1, count + 1, k);
if (count + 1 == k) {
//Display the result value
for (int i = 0; i < k; ++i) {
cout << " " << result[i];
}
cout << "\n";
}
}
};
int main() {
char matrix[][C] = {
{
'A',
'B',
'C',
'D'
},
{
'E',
'F',
'G',
'H'
},
{
'I',
'J',
'K',
'L'
},
{
'M',
'N',
'O',
'P'
},
{
'Q',
'R',
'S',
'T'
},
};
MyMatrix obj = MyMatrix();
char result[R + C - 1];
obj.show_path(matrix, result, 0, 0, 0, R + C - 1);
return 0;
}
Output
A E I M Q R S T
A E I M N R S T
A E I M N O S T
A E I M N O P T
A E I J N R S T
A E I J N O S T
A E I J N O P T
A E I J K O S T
A E I J K O P T
A E I J K L P T
A E F J N R S T
A E F J N O S T
A E F J N O P T
A E F J K O S T
A E F J K O P T
A E F J K L P T
A E F G K O S T
A E F G K O P T
A E F G K L P T
A E F G H L P T
A B F J N R S T
A B F J N O S T
A B F J N O P T
A B F J K O S T
A B F J K O P T
A B F J K L P T
A B F G K O S T
A B F G K O P T
A B F G K L P T
A B F G H L P T
A B C G K O S T
A B C G K O P T
A B C G K L P T
A B C G H L P T
A B C D H L P T
/*
Java Program
Print all possible paths from top left to bottom right of matrix
*/
public class MyMatrix {
public int rows;
public int cols;
public MyMatrix(char [][]matrix)
{
//Get the size of matrix
rows = matrix.length;
cols = matrix[0].length;
}
//Display of all path of top to bottom and left to right
void show_path(char [][]matrix,char []result,int row ,int col,int count,int k)
{
if(row >= this.rows || col >= this.cols)
{
return;
}
result[count]=matrix[row][col];
//recursive execute method with new parameters
show_path(matrix,result,row+1,col,count+1,k);
show_path(matrix,result,row,col+1,count+1,k);
if(count+1==k)
{
//Display the result value
for (int i = 0; i <k; ++i)
{
System.out.print(" "+result[i]);
}
System.out.print("\n");
}
}
public static void main(String[] args) {
char [][]matrix = {
{'A', 'B', 'C', 'D'},
{'E', 'F', 'G', 'H'},
{'I', 'J', 'K', 'L'},
{'M', 'N', 'O', 'P'},
{'Q', 'R', 'S', 'T'},
};
MyMatrix obj = new MyMatrix(matrix);
//Auxiliary memory which are storing path result
char []result= new char[obj.rows+obj.cols-1];
obj.show_path(matrix,result,0,0,0,obj.rows+obj.cols-1);
}
}
Output
A E I M Q R S T
A E I M N R S T
A E I M N O S T
A E I M N O P T
A E I J N R S T
A E I J N O S T
A E I J N O P T
A E I J K O S T
A E I J K O P T
A E I J K L P T
A E F J N R S T
A E F J N O S T
A E F J N O P T
A E F J K O S T
A E F J K O P T
A E F J K L P T
A E F G K O S T
A E F G K O P T
A E F G K L P T
A E F G H L P T
A B F J N R S T
A B F J N O S T
A B F J N O P T
A B F J K O S T
A B F J K O P T
A B F J K L P T
A B F G K O S T
A B F G K O P T
A B F G K L P T
A B F G H L P T
A B C G K O S T
A B C G K O P T
A B C G K L P T
A B C G H L P T
A B C D H L P T
/*
C# Program
Print all possible paths from top left to bottom right of matrix
*/
using System;
public class MyMatrix {
public int rows;
public int cols;
public MyMatrix(char[,] matrix) {
//Get the size of matrix
rows = matrix.GetLength(0);
cols = matrix.GetLength(1);
}
//Display of all path of top to bottom and left to right
void show_path(char[,] matrix, char[] result, int row, int col, int count, int k) {
if (row >= this.rows || col >= this.cols) {
return;
}
result[count] = matrix[row,col];
show_path(matrix, result, row + 1, col, count + 1, k);
show_path(matrix, result, row, col + 1, count + 1, k);
if (count + 1 == k) {
//Display the result value
for (int i = 0; i < k; ++i) {
Console.Write(" " + result[i]);
}
Console.Write("\n");
}
}
public static void Main(String[] args) {
char[,] matrix = {
{
'A',
'B',
'C',
'D'
},
{
'E',
'F',
'G',
'H'
},
{
'I',
'J',
'K',
'L'
},
{
'M',
'N',
'O',
'P'
},
{
'Q',
'R',
'S',
'T'
},
};
MyMatrix obj = new MyMatrix(matrix);
char[]
//Auxiliary memory which are storing path result
result = new char[obj.rows + obj.cols - 1];
obj.show_path(matrix, result, 0, 0, 0, obj.rows + obj.cols - 1);
}
}
Output
A E I M Q R S T
A E I M N R S T
A E I M N O S T
A E I M N O P T
A E I J N R S T
A E I J N O S T
A E I J N O P T
A E I J K O S T
A E I J K O P T
A E I J K L P T
A E F J N R S T
A E F J N O S T
A E F J N O P T
A E F J K O S T
A E F J K O P T
A E F J K L P T
A E F G K O S T
A E F G K O P T
A E F G K L P T
A E F G H L P T
A B F J N R S T
A B F J N O S T
A B F J N O P T
A B F J K O S T
A B F J K O P T
A B F J K L P T
A B F G K O S T
A B F G K O P T
A B F G K L P T
A B F G H L P T
A B C G K O S T
A B C G K O P T
A B C G K L P T
A B C G H L P T
A B C D H L P T
# Python 3 Program
# Print all possible paths from top left to bottom right of matrix
class MyMatrix :
def __init__(self, matrix) :
# Get the size of matrix
self.rows = len(matrix)
self.cols = len(matrix[0])
# Display of all path of top to bottom and left to right
def show_path(self, matrix, result, row, col, count, k) :
if (row >= self.rows or col >= self.cols) :
return
result[count] = matrix[row][col]
# recursive execute method with new parameters
self.show_path(matrix, result, row + 1, col, count + 1, k)
self.show_path(matrix, result, row, col + 1, count + 1, k)
if (count + 1 == k) :
i = 0
# Display the result value
while (i < k) :
print(" ", result[i], end = "")
i += 1
print("\n", end = "")
def main() :
matrix = [
['A', 'B', 'C', 'D'],
['E', 'F', 'G', 'H'],
['I', 'J', 'K', 'L'],
['M', 'N', 'O', 'P'],
['Q', 'R', 'S', 'T']
]
obj = MyMatrix(matrix)
# Auxiliary memory which are storing path result
result = [' '] * (obj.rows + obj.cols - 1)
obj.show_path(matrix, result, 0, 0, 0, obj.rows + obj.cols - 1)
if __name__ == "__main__":
main()
Output
A E I M Q R S T
A E I M N R S T
A E I M N O S T
A E I M N O P T
A E I J N R S T
A E I J N O S T
A E I J N O P T
A E I J K O S T
A E I J K O P T
A E I J K L P T
A E F J N R S T
A E F J N O S T
A E F J N O P T
A E F J K O S T
A E F J K O P T
A E F J K L P T
A E F G K O S T
A E F G K O P T
A E F G K L P T
A E F G H L P T
A B F J N R S T
A B F J N O S T
A B F J N O P T
A B F J K O S T
A B F J K O P T
A B F J K L P T
A B F G K O S T
A B F G K O P T
A B F G K L P T
A B F G H L P T
A B C G K O S T
A B C G K O P T
A B C G K L P T
A B C G H L P T
A B C D H L P T
# Ruby Program
# Print all possible paths from top left to bottom right of matrix
class MyMatrix
# Define the accessor and reader of class MyMatrix
attr_reader :rows, :cols
attr_accessor :rows, :cols
def initialize(matrix)
# Get the size of matrix
@rows = matrix.length
@cols = matrix[0].length
end
# Display of all path of top to bottom and left to right
def show_path(matrix, result, row, col, count, k)
if (row >= self.rows || col >= self.cols)
return
end
result[count] = matrix[row][col]
# recursive execute method with new parameters
self.show_path(matrix, result, row + 1, col, count + 1, k)
self.show_path(matrix, result, row, col + 1, count + 1, k)
if (count + 1 == k)
i = 0
# Display the result value
while (i < k)
print(" ", result[i])
i += 1
end
print("\n")
end
end
end
def main()
matrix = [
['A', 'B', 'C', 'D'],
['E', 'F', 'G', 'H'],
['I', 'J', 'K', 'L'],
['M', 'N', 'O', 'P'],
['Q', 'R', 'S', 'T']
]
obj = MyMatrix.new(matrix)
# Auxiliary memory which are storing path result
result = Array.new(obj.rows + obj.cols - 1, ' ' )
obj.show_path(matrix, result, 0, 0, 0, obj.rows + obj.cols - 1)
end
main()
Output
A E I M Q R S T
A E I M N R S T
A E I M N O S T
A E I M N O P T
A E I J N R S T
A E I J N O S T
A E I J N O P T
A E I J K O S T
A E I J K O P T
A E I J K L P T
A E F J N R S T
A E F J N O S T
A E F J N O P T
A E F J K O S T
A E F J K O P T
A E F J K L P T
A E F G K O S T
A E F G K O P T
A E F G K L P T
A E F G H L P T
A B F J N R S T
A B F J N O S T
A B F J N O P T
A B F J K O S T
A B F J K O P T
A B F J K L P T
A B F G K O S T
A B F G K O P T
A B F G K L P T
A B F G H L P T
A B C G K O S T
A B C G K O P T
A B C G K L P T
A B C G H L P T
A B C D H L P T
<?php
/*
Php Program
Print all possible paths from top left to bottom right of matrix
*/
class MyMatrix {
public $rows;
public $cols;
function __construct($matrix) {
//Get the size of matrix
$this->rows = count($matrix);
$this->cols = count($matrix[0]);
}
//Display of all path of top to bottom and left to right
function show_path($matrix, &$result, $row, $col, $count, $k) {
if ($row >= $this->rows || $col >= $this->cols) {
return;
}
$result[$count] = $matrix[$row][$col];
//recursive execute method with new parameters
$this->show_path($matrix, $result, $row + 1, $col, $count + 1, $k);
$this->show_path($matrix, $result, $row, $col + 1, $count + 1, $k);
if ($count + 1 == $k) {
//Display the result value
for ($i = 0; $i < $k; ++$i) {
echo(" ". $result[$i]);
}
echo("\n");
}
}
}
function main() {
$matrix = array(
array('A', 'B', 'C', 'D'),
array('E', 'F', 'G', 'H'),
array('I', 'J', 'K', 'L'),
array('M', 'N', 'O', 'P'),
array('Q', 'R', 'S', 'T')
);
$obj = new MyMatrix($matrix);
//Auxiliary memory which are storing path result
$result = array_fill(0, $obj->rows + $obj->cols - 1," " );
$obj->show_path($matrix, $result, 0, 0, 0, $obj->rows + $obj->cols - 1);
}
main();
Output
A E I M Q R S T
A E I M N R S T
A E I M N O S T
A E I M N O P T
A E I J N R S T
A E I J N O S T
A E I J N O P T
A E I J K O S T
A E I J K O P T
A E I J K L P T
A E F J N R S T
A E F J N O S T
A E F J N O P T
A E F J K O S T
A E F J K O P T
A E F J K L P T
A E F G K O S T
A E F G K O P T
A E F G K L P T
A E F G H L P T
A B F J N R S T
A B F J N O S T
A B F J N O P T
A B F J K O S T
A B F J K O P T
A B F J K L P T
A B F G K O S T
A B F G K O P T
A B F G K L P T
A B F G H L P T
A B C G K O S T
A B C G K O P T
A B C G K L P T
A B C G H L P T
A B C D H L P T
/*
Scala Program
Print all possible paths from top left to bottom right of matrix
*/
class MyMatrix(var rows: Int,
var cols: Int) {
def this(matrix: Array[Array[Char]]) {
//Get the size of matrix
this(matrix.length, matrix(0).length);
}
//Display of all path of top to bottom and left to right
def show_path(matrix: Array[Array[Char]], result: Array[Char], row: Int, col: Int, count: Int, k: Int): Unit = {
if (row >= this.rows || col >= this.cols) {
return;
}
result(count) = matrix(row)(col);
//recursive execute method with new parameters
this.show_path(matrix, result, row + 1, col, count + 1, k);
this.show_path(matrix, result, row, col + 1, count + 1, k);
if (count + 1 == k) {
var i: Int = 0;
//Display the result value
while (i < k) {
print(" " + result(i));
i += 1;
}
print("\n");
}
}
}
object Main {
def main(args: Array[String]): Unit = {
val matrix: Array[Array[Char]] = Array(
Array('A', 'B', 'C', 'D'),
Array('E', 'F', 'G', 'H'),
Array('I', 'J', 'K', 'L'),
Array('M', 'N', 'O', 'P'),
Array('Q', 'R', 'S', 'T'));
val obj: MyMatrix = new MyMatrix(matrix);
//Auxiliary memory which are storing path result
var result: Array[Char] = Array.fill[Char](obj.rows + obj.cols - 1)(' ');
obj.show_path(matrix, result, 0, 0, 0, obj.rows + obj.cols - 1);
}
}
Output
A E I M Q R S T
A E I M N R S T
A E I M N O S T
A E I M N O P T
A E I J N R S T
A E I J N O S T
A E I J N O P T
A E I J K O S T
A E I J K O P T
A E I J K L P T
A E F J N R S T
A E F J N O S T
A E F J N O P T
A E F J K O S T
A E F J K O P T
A E F J K L P T
A E F G K O S T
A E F G K O P T
A E F G K L P T
A E F G H L P T
A B F J N R S T
A B F J N O S T
A B F J N O P T
A B F J K O S T
A B F J K O P T
A B F J K L P T
A B F G K O S T
A B F G K O P T
A B F G K L P T
A B F G H L P T
A B C G K O S T
A B C G K O P T
A B C G K L P T
A B C G H L P T
A B C D H L P T
/*
Swift Program
Print all possible paths from top left to bottom right of matrix
*/
class MyMatrix {
var rows: Int;
var cols: Int;
init(_ matrix: [[Character]]) {
//Get the size of matrix
self.rows = matrix.count;
self.cols = matrix[0].count;
}
//Display of all path of top to bottom and left to right
func show_path(_ matrix: [[Character]], _ result: inout [Character], _ row: Int, _ col: Int, _ count: Int, _ k: Int) {
if (row >= self.rows || col >= self.cols) {
return;
}
result[count] = matrix[row][col];
//recursive execute method with new parameters
self.show_path(matrix, &result, row + 1, col, count + 1, k);
self.show_path(matrix, &result, row, col + 1, count + 1, k);
if (count + 1 == k) {
var i: Int = 0;
//Display the result value
while (i < k) {
print(" ", result[i], terminator: "");
i += 1;
}
print("\n", terminator: "");
}
}
}
func main() {
let matrix: [
[Character]
] = [
["A", "B", "C", "D"],
["E", "F", "G", "H"],
["I", "J", "K", "L"],
["M", "N", "O", "P"],
["Q", "R", "S", "T"]
];
let obj: MyMatrix = MyMatrix(matrix);
//Auxiliary memory which are storing path result
var result: [Character] = Array(repeating:" " , count: obj.rows + obj.cols - 1);
obj.show_path(matrix, &result, 0, 0, 0, obj.rows + obj.cols - 1);
}
main();
Output
A E I M Q R S T
A E I M N R S T
A E I M N O S T
A E I M N O P T
A E I J N R S T
A E I J N O S T
A E I J N O P T
A E I J K O S T
A E I J K O P T
A E I J K L P T
A E F J N R S T
A E F J N O S T
A E F J N O P T
A E F J K O S T
A E F J K O P T
A E F J K L P T
A E F G K O S T
A E F G K O P T
A E F G K L P T
A E F G H L P T
A B F J N R S T
A B F J N O S T
A B F J N O P T
A B F J K O S T
A B F J K O P T
A B F J K L P T
A B F G K O S T
A B F G K O P T
A B F G K L P T
A B F G H L P T
A B C G K O S T
A B C G K O P T
A B C G K L P T
A B C G H L P T
A B C D H L P T
/*
Node Js Program
Print all possible paths from top left to bottom right of matrix
*/
class MyMatrix {
constructor(matrix) {
//Get the size of matrix
this.rows = matrix.length;
this.cols = matrix[0].length;
}
//Display of all path of top to bottom and left to right
show_path(matrix, result, row, col, count, k) {
if (row >= this.rows || col >= this.cols) {
return;
}
result[count] = matrix[row][col];
//recursive execute method with new parameters
this.show_path(matrix, result, row + 1, col, count + 1, k);
this.show_path(matrix, result, row, col + 1, count + 1, k);
if (count + 1 == k) {
var i = 0;
//Display the result value
while (i < k) {
process.stdout.write(" " + result[i]);
i++;
}
process.stdout.write("\n");
}
}
}
function main(args) {
var matrix = [
['A', 'B', 'C', 'D'],
['E', 'F', 'G', 'H'],
['I', 'J', 'K', 'L'],
['M', 'N', 'O', 'P'],
['Q', 'R', 'S', 'T']
];
var obj = new MyMatrix(matrix);
//Auxiliary memory which are storing path result
var result = Array(obj.rows + obj.cols - 1).fill(' ');
obj.show_path(matrix, result, 0, 0, 0, obj.rows + obj.cols - 1);
}
main();
Output
A E I M Q R S T
A E I M N R S T
A E I M N O S T
A E I M N O P T
A E I J N R S T
A E I J N O S T
A E I J N O P T
A E I J K O S T
A E I J K O P T
A E I J K L P T
A E F J N R S T
A E F J N O S T
A E F J N O P T
A E F J K O S T
A E F J K O P T
A E F J K L P T
A E F G K O S T
A E F G K O P T
A E F G K L P T
A E F G H L P T
A B F J N R S T
A B F J N O S T
A B F J N O P T
A B F J K O S T
A B F J K O P T
A B F J K L P T
A B F G K O S T
A B F G K O P T
A B F G K L P T
A B F G H L P T
A B C G K O S T
A B C G K O P T
A B C G K L P T
A B C G H L P T
A B C D H L P T
Time Complexity Analysis
In the worst case, the algorithm explores all paths from the top-left to the bottom-right corner of the matrix. Since there are 2^(R+C-2) possible paths, the time complexity is exponential, O(2^(R+C-2)).
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment