Check if it is possible to get given sum by taking one element from each row | Function that prints whether is it possible to make sum equal to K ; Base case ; Condition if we can make sum equal to current column by using above rows ; Iterate through current column and check whether we can make sum less than or equal to k ; Printing whether is it possible or not ; Driver Code
def PossibleSum ( n , m , v , k ) : NEW_LINE INDENT dp = [ [ 0 ] * ( k + 1 ) for i in range ( n + 1 ) ] NEW_LINE dp [ 0 ] [ 0 ] = 1 NEW_LINE for i in range ( n ) : NEW_LINE INDENT for j in range ( k + 1 ) : NEW_LINE INDENT if dp [ i ] [ j ] == 1 : NEW_LINE INDENT for d in range ( m ) : NEW_LINE INDENT if ( j + v [ i ] [ d ] ) <= k : NEW_LINE INDENT dp [ i + 1 ] [ j + v [ i ] [ d ] ] = 1 NEW_LINE DEDENT DEDENT DEDENT DEDENT DEDENT if dp [ n ] [ k ] == 1 : NEW_LINE INDENT print ( " YES " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " NO " ) NEW_LINE DEDENT DEDENT N = 2 NEW_LINE M = 10 NEW_LINE K = 5 NEW_LINE arr = [ [ 4 , 0 , 15 , 3 , 2 , 20 , 10 , 1 , 5 , 4 ] , [ 4 , 0 , 10 , 3 , 2 , 25 , 4 , 1 , 5 , 4 ] ] NEW_LINE PossibleSum ( N , M , arr , K ) NEW_LINE