Check if array sum can be made K by three operations on it | Python program to find if Array can have sum of K by applying three types of possible operations on it ; Check if it is possible to achieve a sum with three operation allowed ; if sum id negative . ; If going out of bound . ; If sum is achieved . ; If the current state is not evaluated yet . ; Replacing element with negative value of the element . ; Substracting index number from the element . ; Adding index number to the element . ; Wrapper Function ; Driver Code
MAX = 100 NEW_LINE def check ( i , add , n , k , a , dp ) : NEW_LINE INDENT if add <= 0 : NEW_LINE INDENT return False NEW_LINE DEDENT if i >= n : NEW_LINE INDENT if add == k : NEW_LINE INDENT return True NEW_LINE DEDENT return False NEW_LINE DEDENT if dp [ i ] [ add ] != - 1 : NEW_LINE INDENT return dp [ i ] [ add ] NEW_LINE DEDENT dp [ i ] [ add ] = ( check ( i + 1 , add - 2 * a [ i ] , n , k , a , dp ) or check ( i + 1 , add , n , k , a , dp ) ) NEW_LINE dp [ i ] [ add ] = ( check ( i + 1 , add - ( i + 1 ) , n , k , a , dp ) or dp [ i ] [ add ] ) NEW_LINE dp [ i ] [ add ] = ( check ( i + 1 , add + i + 1 , n , k , a , dp ) or dp [ i ] [ add ] ) NEW_LINE return dp [ i ] [ add ] NEW_LINE DEDENT def wrapper ( n , k , a ) : NEW_LINE INDENT add = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT add += a [ i ] NEW_LINE DEDENT dp = [ - 1 ] * MAX NEW_LINE for i in range ( MAX ) : NEW_LINE INDENT dp [ i ] = [ - 1 ] * MAX NEW_LINE DEDENT return check ( 0 , add , n , k , a , dp ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT a = [ 1 , 2 , 3 , 4 ] NEW_LINE n = 4 NEW_LINE k = 5 NEW_LINE print ( " Yes " ) if wrapper ( n , k , a ) else print ( " No " ) NEW_LINE DEDENT