Print all possible paths from top left to bottom right of matrix
Given a matrix of size m
x n
, the task is to print all possible paths from the top-left cell (0, 0)
to the bottom-right cell (m-1, n-1)
. A path is defined as a sequence of cells starting from (0, 0)
and ending at (m-1, n-1)
, such that we can only move either down or right from any cell in the path.

One way to approach this problem is to use backtracking. We start at the top-left cell (0, 0)
and explore all possible paths by moving either down or right at each step. If we reach the bottom-right cell (m-1, n-1)
, we have found a valid path and print it. Otherwise, we continue exploring all possible paths until all cells have been visited or we reach a dead end.
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
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