Find sub | Javascript implementation of the approach ; Function to return the sum of the sub - matrix ; Function that returns true if it is possible to find the sub - matrix with required sum ; 2 - D array to store the sum of all the sub - matrices ; Filling of dp [ ] [ ] array ; Checking for each possible sub - matrix of size k X k ; Sub - matrix with the given sum not found ; Driver code ; Function call
var N = 4 function getSum ( r1 , r2 , c1 , c2 , dp ) { return dp [ r2 ] [ c2 ] - dp [ r2 ] [ c1 ] - dp [ r1 ] [ c2 ] + dp [ r1 ] [ c1 ] ; } function sumFound ( K , S , grid ) { var dp = Array . from ( Array ( N + 1 ) , ( ) => Array ( N + 1 ) . fill ( 0 ) ) ; for ( var i = 0 ; i < N ; i ++ ) for ( var j = 0 ; j < N ; j ++ ) dp [ i + 1 ] [ j + 1 ] = dp [ i + 1 ] [ j ] + dp [ i ] [ j + 1 ] - dp [ i ] [ j ] + grid [ i ] [ j ] ; for ( var i = 0 ; i < N ; i ++ ) for ( var j = 0 ; j < N ; j ++ ) { var sum = getSum ( i , i + K , j , j + K , dp ) ; if ( sum == S ) return true ; } return false ; } var grid = [ [ 1 , 2 , 3 , 4 ] , [ 5 , 6 , 7 , 8 ] , [ 9 , 10 , 11 , 12 ] , [ 13 , 14 , 15 , 16 ] ] ; var K = 2 ; var S = 14 ; if ( sumFound ( K , S , grid ) ) document . write ( " " ) ; else document . write ( " " ) ;