Count ways to place ' + ' and ' | Function to count number of ways ' + ' and ' - ' operators can be placed in front of array elements to make the sum of array elements equal to K ; Stores sum of the array ; Stores count of 0 s in A [ ] ; Traverse the array ; Update sum ; Update count of 0 s ; Conditions where no arrangements are possible which adds up to K ; Required sum ; Dp array ; Base cases ; Fill the dp array ; Return answer ; Driver Code ; Input ; Function call
def solve ( A , N , K ) : NEW_LINE INDENT sum = 0 NEW_LINE c = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT sum += A [ i ] NEW_LINE if ( A [ i ] == 0 ) : NEW_LINE INDENT c += 1 NEW_LINE DEDENT DEDENT if ( K > sum or ( sum + K ) % 2 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT sum = ( sum + K ) // 2 NEW_LINE dp = [ [ 0 for i in range ( sum + 1 ) ] for j in range ( N + 1 ) ] NEW_LINE for i in range ( sum + 1 ) : NEW_LINE INDENT dp [ 0 ] [ i ] = 0 NEW_LINE DEDENT for i in range ( N + 1 ) : NEW_LINE INDENT dp [ i ] [ 0 ] = 1 NEW_LINE DEDENT for i in range ( 1 , N + 1 , 1 ) : NEW_LINE INDENT for j in range ( 1 , sum + 1 , 1 ) : NEW_LINE INDENT if ( A [ i - 1 ] <= j and A [ i - 1 ] ) : NEW_LINE INDENT dp [ i ] [ j ] = ( dp [ i - 1 ] [ j ] + dp [ i - 1 ] [ j - A [ i - 1 ] ] ) NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] [ j ] = dp [ i - 1 ] [ j ] NEW_LINE DEDENT DEDENT DEDENT return dp [ N ] [ sum ] + pow ( 2 , c ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT A = [ 1 , 1 , 2 , 3 ] NEW_LINE N = len ( A ) NEW_LINE K = 3 NEW_LINE print ( solve ( A , N , K ) ) NEW_LINE DEDENT