Find Sub-Matrix with the Given Sum in C++

In this problem, we are given a 2D matrix of size N*N and two variables sum and size. Our task is to find a sub-matrix with the given sum.

We need to find a sub-matrix of size*size with element sum equal to sum.

Let's take an example to understand the problem,

Input : mat[][] = {
   {1, 5, 7, 9}
   {2, 4, 6, 8}
   {1, 2, 5, 6}
   {3, 6, 9, 3}
}
sum = 22
Size = 2
Output : YES

Explanation −

The submatrix of size k with sum 22 is
{5, 7}
{4, 6}

Solution Approach

A simple solution to the problem is creating all possible size*size sized subarrays, find the sum and then equate it with the given sum value. Return if both are equal.

Another approach is using the concept of dynamic programming Algorithm. In this approach, we will create a DP array which will store the sum till the current index value i.e. DP[i][j] will store the sum of all elements of the array from row index 0 to i and column index 0 to j.

Using this DP array, we will calculate the sum between any two starting index and ending index using the formula,

$$\mathrm{sum((i_s,j_s)to(i_e,j_e))\:=\:DP[i_s][i_s]\:+\:DP[i_e][i_e]\:-\:DP[i_s][i_e]\:-\:DP[i_e][i_s]}$$

Algorithm

Step 1 − Create a DP matrix of size (n+1)*(n+1).

Step 2 − For each element of the matrix, find the sum till the current index.

Step 3 − For all indexes from 0 to n, find the sum of sub-matrix of size size*size. Using the formula and store in currSum.

Step 4 − if currSum == sum, return true.

Step 5 − return false.

Example

Program to illustrate the working of our solution

#include <iostream>
using namespace std;
#define N 4
bool findSubMatWithSum(int size, int sum, int mat[N][N]){
   int DP[N + 1][N + 1];
   for (int i = 0; i < N; i++)
   for (int j = 0; j < N; j++)
   DP[i + 1][j + 1] = DP[i + 1][j] + DP[i][j + 1] - DP[i][j] + mat[i][j];
   int currSum = 0;
   for (int i = 0; i < N; i++)
   for (int j = 0; j < N; j++) {
      currSum = DP[i][j] + DP[(i + size)][(j + size)] - DP[(i + size)][j] - DP[i][(j + size)];
      if (currSum == sum)
      return true;
   }
   return false;
}
int main(){
   int mat[N][N] = { { 1, 5, 7, 9 },
   { 2, 4, 6, 8 },
   { 1, 2, 5, 6 },
   { 3, 6, 9, 3 } };
   int size = 2;
   int sum = 22;
   if (findSubMatWithSum(size, sum, mat))
      cout<<"Sub-Matrix of given size having the given sum is possible!";
   else
     cout<<"Sub-Matrix of given size having the given sum is not possible!";
}

Output

Sub-Matrix of given size having the given sum is possible!