Check if K can be obtained by performing arithmetic operations on any permutation of an Array | C ++ program for the above approach ; Function that finds the string of possible combination of operations ; If only one number left then check for result ; If resultant value is K ; Else return 0 ; Choose all combination of numbers and operators and operate them ; Choose the first two and operate it with ' + ' ; Place it to 0 th position ; Place ( n - 1 ) th element on 1 st position ; Evaluate the expression with current combination ; Now , we have N - 1 elements ; Try ' - ' operation ; Evaluate the expression with current combination ; Try reverse ' - ' ; Evaluate the expression with current combination ; Try ' * ' operation ; Evaluate the expression with current combination ; Try ' / ' ; Evaluate the expression with current combination ; Try reverse ' / ' ; Evaluate the expression with current combination ; Backtracking Step ; Return 0 if there doesnt exist any combination that gives K ; Function that finds the possible combination of operation to get the resultant value K ; Store the resultant operation ; Function Call ; Driver Code ; Given array arr [ ] ; Resultant value K ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool find ( vector < double > & v , int n , double dest , string s ) { if ( n == 1 ) { if ( abs ( v [ 0 ] - dest ) <= 0.0000001 ) { cout << s + to_string ( int ( dest ) ) << " ▁ " ; return 1 ; } return 0 ; } for ( int i = 0 ; i < n ; i ++ ) { for ( int j = i + 1 ; j < n ; j ++ ) { double a = v [ i ] , b = v [ j ] ; string p = s ; v [ i ] = a + b ; v [ j ] = v [ n - 1 ] ; s = ( s + to_string ( int ( a ) ) + ' + ' + to_string ( int ( b ) ) + " ▁ = > ▁ " ) ; if ( find ( v , n - 1 , dest , s ) ) return 1 ; s = p ; v [ i ] = a - b ; v [ j ] = v [ n - 1 ] ; s = ( s + to_string ( int ( a ) ) + ' - ' + to_string ( int ( b ) ) + " ▁ = > ▁ " ) ; if ( find ( v , n - 1 , dest , s ) ) return 1 ; s = p ; v [ i ] = b - a ; v [ j ] = v [ n - 1 ] ; s = ( s + to_string ( int ( b ) ) + ' - ' + to_string ( int ( a ) ) + " ▁ = > ▁ " ) ; if ( find ( v , n - 1 , dest , s ) ) return 1 ; s = p ; v [ i ] = a * b ; v [ j ] = v [ n - 1 ] ; s = ( s + to_string ( int ( a ) ) + ' * ' + to_string ( int ( b ) ) + " ▁ = > ▁ " ) ; if ( find ( v , n - 1 , dest , s ) ) return 1 ; s = p ; if ( b != 0 ) { v [ i ] = a / b ; v [ j ] = v [ n - 1 ] ; s = ( s + to_string ( int ( a ) ) + ' / ' + to_string ( int ( b ) ) + " ▁ = > ▁ " ) ; if ( find ( v , n - 1 , dest , s ) ) return 1 ; } s = p ; if ( a != 0 ) { v [ i ] = b / a ; v [ j ] = v [ n - 1 ] ; s = ( s + to_string ( int ( b ) ) + ' / ' + to_string ( int ( a ) ) + " ▁ = > ▁ " ) ; if ( find ( v , n - 1 , dest , s ) ) return 1 ; } s = p ; v [ i ] = a ; v [ j ] = b ; } } return 0 ; } void checkPossibleOperation ( vector < double > & arr , double K ) { string s = " " ; if ( ! find ( arr , arr . size ( ) , K , s ) ) { cout << " - 1" ; } } int main ( ) { vector < double > arr = { 2 , 0 , 0 , 2 } ; double K = 4 ; checkPossibleOperation ( arr , K ) ; return 0 ; }