Find sub | Python 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
N = 4 NEW_LINE def getSum ( r1 , r2 , c1 , c2 , dp ) : NEW_LINE INDENT return dp [ r2 ] [ c2 ] - dp [ r2 ] [ c1 ] - dp [ r1 ] [ c2 ] + dp [ r1 ] [ c1 ] NEW_LINE DEDENT def sumFound ( K , S , grid ) : NEW_LINE INDENT dp = [ [ 0 for i in range ( N + 1 ) ] for j in range ( N + 1 ) ] NEW_LINE for i in range ( N ) : NEW_LINE INDENT for j in range ( N ) : NEW_LINE INDENT dp [ i + 1 ] [ j + 1 ] = dp [ i + 1 ] [ j ] + dp [ i ] [ j + 1 ] - dp [ i ] [ j ] + grid [ i ] [ j ] NEW_LINE DEDENT DEDENT for i in range ( 0 , N ) : NEW_LINE INDENT for j in range ( 0 , N ) : NEW_LINE INDENT sum = getSum ( i , i + K , j , j + K , dp ) NEW_LINE if ( sum == S ) : NEW_LINE INDENT return True NEW_LINE DEDENT DEDENT DEDENT return False NEW_LINE DEDENT grid = [ [ 1 , 2 , 3 , 4 ] , [ 5 , 6 , 7 , 8 ] , [ 9 , 10 , 11 , 12 ] , [ 13 , 14 , 15 , 16 ] ] NEW_LINE K = 2 NEW_LINE S = 14 NEW_LINE if ( sumFound ( K , S , grid ) ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT