# Find Sum of all Submatrices of a Given Matrix

**Problem**

You are given a N * N 2D Matrix.

Your task is to find sum of all possible submatrices. Which can be produced from this matrix.

Have a look at input and output for better understanding.

**Input**

`arr[] = {{1, 1}, {1, 1}};`

**Output**

`16`

**Explanatation**

Sum of sub matrices with size 1 = 1*4 = 4

Sum of sub matrices with size 2 = 2*4 = 8

Similarly, Sum of sub matrices with size 3 = 3 * 0 (since, no 3 * 3 matrix is possible) = 0

Sum of sub matrices with size 4 = 4*1 =4

Hence, total sum = 4 + 8 + 0 + 4 = 16.

Have a look at another example too.

**Input**

`arr[] = {{1, 2, 3},{4, 5, 6}, {7, 8, 9}}`

**Output**

`500`

**Solution**

**Brute force** - We can solve this question just by traversing the whole matrix N times and generating and calculating their sums.

But problem, is this is very in efficient way to solve this problem. Once, the size of matrix gets bigger, it will be very time consuming and start producing TLE in competitve programming. Time complexity of this soltuion will be **O(n ^{6})**.

**Tricky Solution** -

Key here is to understand the relation. Let's beak it down.

We'll first find out, how many times an element of matirix can occur in submatrices.

Let's call this element **Arr(x,y)**. Where **x** and **y** is position of element in 0 based indexing.

So total occurance of **Arr(x,y)** will be **(X + 1) * (Y + 1) * (N – X) * (N – Y)**.

Let's call this total number of occurance be **S(x,y)**.

So, total sum of produced by this element will be** Arr(x,y) * S(x,y).**

Now, we can figure out total sum of submatrices by adding total sum of all the elements of matrix.

Let's code it.

```
#include <iostream>
using namespace std;
int matrixSum(int arr[][3])
{
int sum = 0; // this will store total sum
// Find out number of submatrices, each element belongs to
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
// Number of ways to choose
// from top-left elements
int top_left = (i + 1) * (j + 1);
// Number of ways to choose
// from bottom-right elements
int bottom_right = (n - i) * (n - j);
sum += (top_left * bottom_right * arr[i][j]);
}
return sum;
}
// Main Function
int main()
{
int arr[3][3] = { { 1, 1, 1 },
{ 1, 1, 1 },
{ 1, 1, 1 } };
cout << matrixSum(arr);
return 0;
}
```

This will produce the follwing output.

`100`