[C++] Easy Solution with Explanation
Intution :\n We need to apply same logic which we used in : Subarray Sum Equals K. If you have not done this pls check it out first .\n Calculate prefix sum for
**Intution :**\n* We need to apply same logic which we used in : **[Subarray Sum Equals K](https://leetcode.com/problems/subarray-sum-equals-k/)**. If you have not done this pls check it out first .\n* Calculate prefix sum for each row.\n* Calculate  sum for each column and check if **sum - target** is there in the DS or not .If it is there then add the count. (DS is data structure , in this question we will use **`unordered_map<int,int> counter`**)\n\t\t** Why sum - target ? Because if sum - target is there in the DS it means that there is a subset whose sum == target.\n\t\tExample :   target = 4 \n\t\t***1***  *1  1*  1 \n\t\t***1***  *1  1*  1 \n\t\tsum of bold = 2 , sum of bold + Italic = 6 ,,, 6 - 4 = **2** , it means the italic sub matrix sum = target.\n\n\n**Example** : 4 * 4 matrix , target = 4,\n```\n1 1 1 1\n1 1 1 1\n1 1 1 1\n1 1 1 1\n```\n**1. Calculate prefix sum for each row ;**\n\n```\n1 2 3 4\n1 2 3 4\n1 2 3 4\n1 2 3 4\n```\n\n**2. For every possible range between two columns, accumulate the prefix sum of submartrixes that can be formed between these two columns by adding up the sum of values between these two columns for every row.**\n\nFor first column  :\n![image](https://assets.leetcode.com/users/images/01ff2db8-d070-445b-b67a-d074f1d454ab_1618661347.535767.png)\n\n\n```\nSum = 1 + 1 + 1 + 1 =4\nsum - target =  0 , which is there in map so count will be increased by 1.\n```\n\nFor second column  :\n![image](https://assets.leetcode.com/users/images/c4b0a598-85e5-40cd-8c32-7eeb643bec5b_1618661383.5533128.png)\n\n\nHere   when row = 1 ,  2 - target is not there in the DS so we will add  2 into DS with count 1,  **sum = 2**     `DS : {{0 , 1 } , {2 , 1}`\nwhen row = 2  , **sum = 4** 4 - target is there so increase count. `DS : {{0 , 1 } , {2 , 1} , { 4 ,1}`\nwhen row = 3  , **sum = 6** 6 - target = 2, which is there in DS so increase count.`DS : {{0 , 1 } , {2 , 1} , { 4 ,1} ,{6,1}`\nwhen row = 4 , **sum = 8** 8 - target = 4 , which is there in DS so increase count. `DS : {{0 , 1 } , {2 , 1} , { 4 ,1} ,{6,1}, {8,1}`\n\n**In this way for each column we will get number of sub matrixes whose sum is equals to target. Like wise we will do this for all the columns . Now the problem is in this way we are missing some  sub matrixes**\n![image](https://assets.leetcode.com/users/images/bc2d358c-f1ad-463d-9f10-87e0e0c1fb9c_1618662144.7394516.png)\n\nAs you can see in the image for column 2 we have considered 3 sub matrixes :\n1. Yellow 1\'s\n2. boxes with color inside it.\n3. Red border color boxes. so **what we missed ?????**\n![image](https://assets.leetcode.com/users/images/a010166e-ffcd-4ad9-95b4-77240850a0f4_1618662409.24798.png)\n**We missed the 1\'s in green box. So to count those sub matrixes  we need to subtract  previous column sum. For this third loop is there which checks if column start is greater than 0  then subtract the sum of previous column and sum.**\n\n```\nclass Solution {\npublic:\n    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {\n        int rows = matrix.size() , cols = matrix[0].size();\n        \n        if(rows < 1){\n            return 0;\n        }\n        \n        // calculate prefix sum for rows\n        for(int row = 0 ; row < rows ; row++){\n            for(int col = 1 ; col < cols ;col++){\n                matrix[row][col] =  matrix[row][col] + matrix[row][col -1];\n            }\n        }\n      \n        int count = 0 , sum ;\n        unordered_map<int , int> counter;\n        for(int colstart = 0 ; colstart < cols ;colstart++){\n            for(int col = colstart ; col < cols; col++){\n                counter.clear();\n                counter[0] = 1;\n                sum =0;\n                for(int row = 0 ; row < rows ;row++){\n                    sum += matrix[row][col] - (colstart > 0 ? matrix[row][colstart - 1] : 0 );\n                    count += (counter.find(sum- target) != counter.end() ? counter[sum-target] : 0);\n                    counter[sum]++;\n                }\n            }\n        }\n        return count;\n    }\n};\n```\n\n***Time Complexity   :  O(row * column^2)\nSpace Complexity :O(N)***\n\n**Update 18/04/2021 :**\n\nIncase anyone else is having same doubt : \n![image](https://assets.leetcode.com/users/images/11c39b8e-da66-438b-8d50-bb8ac7f23b00_1618745215.816512.png)\n\n**Hello,\n\tFeel free to comment for doubts . I will love to clear them . If something is wrong please let me know in comment section.\nThanks !! Happy Coding.**
['C', 'C++']