Skip to main content

Minimum sum path in a Matrix

In a matrix, which is a grid of numbers, we want to find the path with the minimum sum of numbers from the top left corner to the bottom right corner. We can only move down or right from each cell.

Finding the minimum sum path in a matrix using recursion is a common problem in computer science. The problem involves finding the path with the lowest sum of values from the top left corner of a matrix to the bottom right corner, only moving down or right at each step.

Recursion is a technique where a function calls itself repeatedly until it reaches a base case. In the case of finding the minimum sum path in a matrix, the base cases are when the function reaches the last row or column of the matrix, at which point it can only move in one direction.

The recursive function takes as input the matrix, the current row and column indices, and the current sum of values along the path. It then recursively calls itself, passing in the new row and column indices and the updated sum of values, until it reaches the base case.

At each step, the function compares the sum of the current path to the minimum sum found so far. If the current sum is smaller, it updates the minimum sum and stores the path taken to reach it.

Once the function has reached the base case, it returns the minimum sum and the path taken to achieve it. The main program then prints out the minimum sum and the path taken.

Overall, finding the minimum sum path in a matrix using recursion can be a powerful tool in computer science and can be used in a variety of applications.

Code Solution

// C Program
// Minimum sum path in a Matrix
#include <stdio.h>
#include <limits.h>

#define R 5
#define C 8 

// Find the path sum of (0,0) to Matrix (R-1,C-1) 
void path_sum(int matrix[R][C],int *output,int i ,int j,int count,int k,int sum)
{

  if(count==k && *output > sum)
  {
    // When get a new result
    *output = sum;
  }
  else if(i < R && j < C)
  {
    //Recursive execute method with new parameters
    path_sum(matrix,output,i+1,j,count+1,k,sum+matrix[i][j]);
    path_sum(matrix,output,i,j+1,count+1,k,sum+matrix[i][j]);
  }
}

// Handles the request to find minimum path sum in a matrix
void minimum_path_sum(int matrix[R][C])
{
    // Set initially max value
    int output = INT_MAX;

    // Calculate max path sum
    path_sum(matrix,&output,0,0,0,R+C-1,0);

    // Display find result
    printf(" %d \n",output);
}

int main()
{
    // Define element of matrix
    int matrix[R][C] =
    {
        {1,  3,  4, 6,  8, 2,  4, 15 },
        {2,  10, 1, 4,  5, 7,  7, 2  },
        {13, 3,  1, 3,  1, 7,  4, 12 },
        {5,  8,  1, 7,  2, 7,  4, 2  },
        {7,  9,  3, 13, 5, 10, 3, 2  }
    };
    // 1 -> 3 -> 4 -> 1 -> 1 -> 3 -> 1 -> 2 -> 7 -> 4 -> 2 -> 2
    minimum_path_sum(matrix);

  return 0;
}

Output

 31
/*
    Java program 
    Minimum sum path in a Matrix
*/
// Define TreeNode
public class MyMatrix
{
    public int output;
    // Find the path sum of (0,0) to Matrix (R-1,C-1) 
    public void path_sum(int[][] matrix, 
    int i, int j, 
    int count, int k, 
    int sum, 
    int rows, int cols)
    {
        if (count == k && this.output > sum)
        {
            // When get a new result
            this.output = sum;
        }
        else if (i < rows && j < cols)
        {
            //Recursive execute method with new parameters
            path_sum(matrix, i + 1, j, count + 1, k, sum + matrix[i][j],rows,cols);
            path_sum(matrix, i, j + 1, count + 1, k, sum + matrix[i][j],rows,cols);
        }
    }
    // Handles the request to find max path sum in a matrix
    public void minimum_path_sum(int[][] matrix)
    {
        int r = matrix.length;
        int c = matrix[0].length;
        // Set initially max value
        this.output = Integer.MAX_VALUE;
        // Calculate max path sum
        path_sum(matrix, 0, 0, 0, r + c - 1, 0, r, c);
        // Display find result
        System.out.print("  " + this.output + " \n");
    }
    public static void main(String[] args)
    {
        MyMatrix obj = new MyMatrix();
        int[][] matrix =
        {
            {1,  3,  4, 6,  8, 2,  4, 15 },
            {2,  10, 1, 4,  5, 7,  7, 2  },
            {13, 3,  1, 3,  1, 7,  4, 12 },
            {5,  8,  1, 7,  2, 7,  4, 2  },
            {7,  9,  3, 13, 5, 10, 3, 2  }
        };
         // 1 -> 3 -> 4 -> 1 -> 1 -> 3 -> 1 -> 2 -> 7 -> 4 -> 2 -> 2
        obj.minimum_path_sum(matrix);
    }
}

Output

  31
// Include header file
#include <iostream>
#include<limits.h>
#define R 5
#define C 8 

using namespace std;
/*
    C++ program 
    Minimum sum path in a Matrix
*/
//  Define TreeNode
class MyMatrix
{
	public: int output;
	//  Find the path sum of (0,0) to Matrix (R-1,C-1)
	void path_sum(int matrix[R][C], int i, int j, int count, int k, int sum)
	{
		if (count == k && this->output > sum)
		{
			//  When get a new result
			this->output = sum;
		}
		else if (i < R && j < C)
		{
			// Recursive execute method with new parameters
			this->path_sum(matrix, i + 1, j, count + 1, k, sum + matrix[i][j]);
			this->path_sum(matrix, i, j + 1, count + 1, k, sum + matrix[i][j]);
		}
	}
	//  Handles the request to find max path sum in a matrix
	void minimum_path_sum(int matrix[R][C])
	{
		
		//  Set initially max value
		this->output = INT_MAX;
		//  Calculate max path sum
		this->path_sum(matrix, 0, 0, 0, R + C - 1, 0);
		//  Display find result
		cout << "  " << this->output << " \n";
	}
};
int main()
{
	MyMatrix obj = MyMatrix();
    int matrix[R][C] =
    {
        {1,  3,  4, 6,  8, 2,  4, 15 },
        {2,  10, 1, 4,  5, 7,  7, 2  },
        {13, 3,  1, 3,  1, 7,  4, 12 },
        {5,  8,  1, 7,  2, 7,  4, 2  },
        {7,  9,  3, 13, 5, 10, 3, 2  }
    };
	//  1->3->4->1->1->3->1->2->7->4->2->2
	obj.minimum_path_sum(matrix);
	return 0;
}

Output

  31
// Include namespace system
using System;
/*
    C# program 
    Minimum sum path in a Matrix
*/
//  Define TreeNode
public class MyMatrix
{
	public int output;
	//  Find the path sum of (0,0) to Matrix (R-1,C-1)
	public void path_sum(int[,] matrix, int i, int j, int count, int k, int sum, int rows, int cols)
	{
		if (count == k && this.output > sum)
		{
			//  When get a new result
			this.output = sum;
		}
		else if (i < rows && j < cols)
		{
			// Recursive execute method with new parameters
			path_sum(matrix, i + 1, j, count + 1, k, sum + matrix[i,j], rows, cols);
			path_sum(matrix, i, j + 1, count + 1, k, sum + matrix[i,j], rows, cols);
		}
	}
	//  Handles the request to find max path sum in a matrix
	public void minimum_path_sum(int[,] matrix)
	{
		int r = matrix.GetLength(0);
		int c = matrix.GetLength(1);
		//  Set initially max value
		this.output = int.MaxValue;
		//  Calculate max path sum
		path_sum(matrix, 0, 0, 0, r + c - 1, 0, r, c);
		//  Display find result
		Console.Write("  " + this.output + " \n");
	}
	public static void Main(String[] args)
	{
		MyMatrix obj = new MyMatrix();
		int[,] matrix = 
        {
            {1,  3,  4, 6,  8, 2,  4, 15 },
            {2,  10, 1, 4,  5, 7,  7, 2  },
            {13, 3,  1, 3,  1, 7,  4, 12 },
            {5,  8,  1, 7,  2, 7,  4, 2  },
            {7,  9,  3, 13, 5, 10, 3, 2  }
        };
		//  1->3->4->1->1->3->1->2->7->4->2->2
		obj.minimum_path_sum(matrix);
	}
}

Output

  31
<?php
/*
    Php program 
    Minimum sum path in a Matrix
*/
//  Define TreeNode
class MyMatrix
{
	public $output;
	//  Find the path sum of (0,0) to Matrix (R-1,C-1)
	public	function path_sum( & $matrix, $i, $j, $count, $k, $sum, $rows, $cols)
	{
		if ($count == $k && $this->output > $sum)
		{
			//  When get a new result
			$this->output = $sum;
		}
		else if ($i < $rows && $j < $cols)
		{
			// Recursive execute method with new parameters
			$this->path_sum($matrix, $i + 1, $j, $count + 1, $k, $sum + $matrix[$i][$j], $rows, $cols);
			$this->path_sum($matrix, $i, $j + 1, $count + 1, $k, $sum + $matrix[$i][$j], $rows, $cols);
		}
	}
	//  Handles the request to find max path sum in a matrix
	public	function minimum_path_sum( & $matrix)
	{
		$r = count($matrix);
		$c = count($matrix[0]);
		//  Set initially max value
		$this->output = PHP_INT_MAX;
		//  Calculate max path sum
		$this->path_sum($matrix, 0, 0, 0, $r + $c - 1, 0, $r, $c);
		//  Display find result
		echo "  ". $this->output ." \n";
	}
}

function main()
{
	$obj = new MyMatrix();
	$matrix = array(
        array(1, 3, 4, 6, 8, 2, 4, 15), 
        array(2, 10, 1, 4, 5, 7, 7, 2), 
        array(13, 3, 1, 3, 1, 7, 4, 12), 
        array(5, 8, 1, 7, 2, 7, 4, 2), 
        array(7, 9, 3, 13, 5, 10, 3, 2)
    );
	//  1->3->4->1->1->3->1->2->7->4->2->2
	$obj->minimum_path_sum($matrix);
}
main();

Output

  31
/*
    Node Js program 
    Minimum sum path in a Matrix
*/
//  Define TreeNode
class MyMatrix
{
	//  Find the path sum of (0,0) to Matrix (R-1,C-1)
	path_sum(matrix, i, j, count, k, sum, rows, cols)
	{
		if (count == k && this.output > sum)
		{
			//  When get a new result
			this.output = sum;
		}
		else if (i < rows && j < cols)
		{
			// Recursive execute method with new parameters
			this.path_sum(matrix, i + 1, j, count + 1, k, sum + matrix[i][j], rows, cols);
			this.path_sum(matrix, i, j + 1, count + 1, k, sum + matrix[i][j], rows, cols);
		}
	}
	//  Handles the request to find max path sum in a matrix
	minimum_path_sum(matrix)
	{
		var r = matrix.length;
		var c = matrix[0].length;
		//  Set initially max value
		this.output = Number.MAX_VALUE;
		//  Calculate max path sum
		this.path_sum(matrix, 0, 0, 0, r + c - 1, 0, r, c);
		//  Display find result
		process.stdout.write("  " + this.output + " \n");
	}
}

function main()
{
	var obj = new MyMatrix();
	var matrix = 
    [
        [1, 3, 4, 6, 8, 2, 4, 15] , 
        [2, 10, 1, 4, 5, 7, 7, 2] , 
        [13, 3, 1, 3, 1, 7, 4, 12] , 
        [5, 8, 1, 7, 2, 7, 4, 2] , 
        [7, 9, 3, 13, 5, 10, 3, 2]
	];
	//  1->3->4->1->1->3->1->2->7->4->2->2
	obj.minimum_path_sum(matrix);
}
main();

Output

  31
import sys

#  Python 3 program 
#  Minimum sum path in a Matrix

#  Define TreeNode
class MyMatrix :
	
	#  Find the path sum of (0,0) to Matrix (R-1,C-1) 
	def path_sum(self, matrix, i, j, count, k, sum, rows, cols) :
		if (count == k and self.output > sum) :
			#  When get a new result
			self.output = sum
		
		elif(i < rows and j < cols) :
			# Recursive execute method with new parameters
			self.path_sum(matrix, i + 1, j, count + 1, k, sum + matrix[i][j], rows, cols)
			self.path_sum(matrix, i, j + 1, count + 1, k, sum + matrix[i][j], rows, cols)
		
	
	#  Handles the request to find max path sum in a matrix
	def minimum_path_sum(self, matrix) :
		r = len(matrix)
		c = len(matrix[0])
		#  Set initially max value
		self.output = sys.maxsize
		#  Calculate max path sum
		self.path_sum(matrix, 0, 0, 0, r + c - 1, 0, r, c)
		#  Display find result
		print("  ", self.output ," ")
	

def main() :
	obj = MyMatrix()
	matrix = [
		[1, 3, 4, 6, 8, 2, 4, 15] , 
        [2, 10, 1, 4, 5, 7, 7, 2] , 
        [13, 3, 1, 3, 1, 7, 4, 12] , 
        [5, 8, 1, 7, 2, 7, 4, 2] , 
        [7, 9, 3, 13, 5, 10, 3, 2]
	]
	#  1->3->4->1->1->3->1->2->7->4->2->2
	obj.minimum_path_sum(matrix)

if __name__ == "__main__": main()

Output

   31
#  Ruby program 
#  Minimum sum path in a Matrix

#  Define TreeNode
class MyMatrix  
	# Define the accessor and reader of class MyMatrix  
	attr_reader :output
	attr_accessor :output
 
	
	#  Find the path sum of (0,0) to Matrix (R-1,C-1) 
	def path_sum(matrix, i, j, count, k, sum, rows, cols) 
		if (count == k && self.output > sum) 
			#  When get a new result
			self.output = sum
		elsif(i < rows && j < cols) 
			# Recursive execute method with new parameters
			self.path_sum(matrix, i + 1, j, count + 1, k, sum + matrix[i][j], rows, cols)
			self.path_sum(matrix, i, j + 1, count + 1, k, sum + matrix[i][j], rows, cols)
		end

	end

	#  Handles the request to find max path sum in a matrix
	def minimum_path_sum(matrix) 
		r = matrix.length
		c = matrix[0].length
		#  Set initially max value
		self.output = (2 ** (0. size * 8 - 2))
		#  Calculate max path sum
		self.path_sum(matrix, 0, 0, 0, r + c - 1, 0, r, c)
		#  Display find result
		print("  ", self.output ," \n")
	end

end

def main() 
	obj = MyMatrix.new()
	matrix = [
		[1, 3, 4, 6, 8, 2, 4, 15] , 
        [2, 10, 1, 4, 5, 7, 7, 2] , 
        [13, 3, 1, 3, 1, 7, 4, 12] , 
        [5, 8, 1, 7, 2, 7, 4, 2] , 
        [7, 9, 3, 13, 5, 10, 3, 2]
	]
	#  1->3->4->1->1->3->1->2->7->4->2->2
	obj.minimum_path_sum(matrix)
end

main()

Output

  31 

/*
    Scala program 
    Minimum sum path in a Matrix
*/
//  Define TreeNode
class MyMatrix(var output: Int)
{
  	def this()
    {
      	this(Int.MaxValue)
    }
	//  Find the path sum of (0,0) to Matrix (R-1,C-1)
	def path_sum(matrix: Array[Array[Int]], i: Int, j: Int, count: Int, k: Int, sum: Int, rows: Int, cols: Int): Unit = {
		if (count == k && this.output > sum)
		{
			//  When get a new result
			this.output = sum;
		}
		else if (i < rows && j < cols)
		{
			// Recursive execute method with new parameters
			this.path_sum(matrix, i + 1, j, count + 1, k, sum + matrix(i)(j), rows, cols);
			this.path_sum(matrix, i, j + 1, count + 1, k, sum + matrix(i)(j), rows, cols);
		}
	}
	//  Handles the request to find max path sum in a matrix
	def minimum_path_sum(matrix: Array[Array[Int]]): Unit = {
		var r: Int = matrix.length;
		var c: Int = matrix(0).length;
		//  Set initially max value
		this.output = Int.MaxValue;
		//  Calculate max path sum
		this.path_sum(matrix, 0, 0, 0, r + c - 1, 0, r, c);
		//  Display find result
		print("  " + this.output + " \n");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: MyMatrix = new MyMatrix();
		var matrix: Array[Array[Int]] = Array(
            Array(1, 3, 4, 6, 8, 2, 4, 15), 
            Array(2, 10, 1, 4, 5, 7, 7, 2), 
            Array(13, 3, 1, 3, 1, 7, 4, 12), 
            Array(5, 8, 1, 7, 2, 7, 4, 2), 
            Array(7, 9, 3, 13, 5, 10, 3, 2)
        );
		//  1->3->4->1->1->3->1->2->7->4->2->2
		obj.minimum_path_sum(matrix);
	}
}

Output

  31
/*
    Swift 4 program 
    Minimum sum path in a Matrix
*/
//  Define TreeNode
class MyMatrix
{
	var output: Int;
	init()
	{
		self.output = Int.max;
	}
	//  Find the path sum of (0,0) to Matrix (R-1,C-1)
	func path_sum(_ matrix: [[Int]], _ i: Int, _ j: Int, _ count: Int, _ k: Int, _ sum: Int, _ rows: Int, _ cols: Int)
	{
		if (count == k && self.output > sum)
		{
			//  When get a new result
			self.output = sum;
		}
		else if (i < rows && j < cols)
		{
			// Recursive execute method with new parameters
			self.path_sum(matrix, i + 1, j, count + 1, k, sum + matrix[i][j], rows, cols);
			self.path_sum(matrix, i, j + 1, count + 1, k, sum + matrix[i][j], rows, cols);
		}
	}
	//  Handles the request to find max path sum in a matrix
	func minimum_path_sum(_ matrix: [[Int]])
	{
		let r: Int = matrix.count;
		let c: Int = matrix[0].count;
		//  Set initially max value
		self.output = Int.max;
		//  Calculate max path sum
		self.path_sum(matrix, 0, 0, 0, r + c - 1, 0, r, c);
		//  Display find result
		print("  ", self.output ," ");
	}
}
func main()
{
	let obj: MyMatrix = MyMatrix();
	let matrix: [[Int]] = 
    [
      [1, 3, 4, 6, 8, 2, 4, 15] , 
      [2, 10, 1, 4, 5, 7, 7, 2] , 
      [13, 3, 1, 3, 1, 7, 4, 12] , 
      [5, 8, 1, 7, 2, 7, 4, 2] , 
      [7, 9, 3, 13, 5, 10, 3, 2]
    ];
	//  1->3->4->1->1->3->1->2->7->4->2->2
	obj.minimum_path_sum(matrix);
}
main();

Output

   31
/*
    Kotlin program 
    Minimum sum path in a Matrix
*/
//  Define TreeNode
class MyMatrix
{
	var output: Int;
	constructor()
	{
		this.output = Int.MAX_VALUE;
	}
	//  Find the path sum of (0,0) to Matrix (R-1,C-1)
	fun path_sum(matrix: Array<Array<Int>> , i: Int, j: Int, count: Int, k: Int, sum: Int, rows: Int, cols: Int): Unit
	{
		if (count == k && this.output>sum)
		{
			//  When get a new result
			this.output = sum;
		}
		else
		if (i<rows && j<cols)
		{
			// Recursive execute method with new parameters
			this.path_sum(matrix, i + 1, j, count + 1, k, sum + matrix[i][j], rows, cols);
			this.path_sum(matrix, i, j + 1, count + 1, k, sum + matrix[i][j], rows, cols);
		}
	}
	//  Handles the request to find max path sum in a matrix
	fun minimum_path_sum(matrix: Array<Array<Int>> ): Unit
	{
		var r: Int = matrix.count();
		var c: Int = matrix[0].count();
		//  Set initially max value
		this.output = Int.MAX_VALUE;
		//  Calculate max path sum
		this.path_sum(matrix, 0, 0, 0, r + c - 1, 0, r, c);
		//  Display find result
		print("  " + this.output + " \n");
	}
}
fun main(args: Array<String>): Unit
{
	var obj: MyMatrix = MyMatrix();
	var matrix: Array<Array<Int>> = arrayOf(
      arrayOf(1, 3, 4, 6, 8, 2, 4, 15), 
      arrayOf(2, 10, 1, 4, 5, 7, 7, 2), 
      arrayOf(13, 3, 1, 3, 1, 7, 4, 12), 
      arrayOf(5, 8, 1, 7, 2, 7, 4, 2), 
      arrayOf(7, 9, 3, 13, 5, 10, 3, 2)
    );
	//  1->3->4->1->1->3->1->2->7->4->2->2
	obj.minimum_path_sum(matrix);
}

Output

  31
Last updated on by Kalkicode




Comment

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