Tug of War | solution by calling itself recursively ; checks whether the it is going out of bound ; checks that the numbers of elements left are not less than the number of elements required to form the solution ; consider the cases when current element is not included in the solution ; add the current element to the solution ; checks if a solution is formed ; checks if the solution formed is better than the best solution so far ; consider the cases where current element is included in the solution ; removes current element before returning to the caller of this function ; main function that generate an arr ; the boolean array that contains the inclusion and exclusion of an element in current set . The number excluded automatically form the other set ; The inclusion / exclusion array for final solution ; Find the solution using recursive function TOWUtil ( ) ; Print the solution ; Driver Code
< ? php function TOWUtil ( & $ arr , $ n , & $ curr_elements , $ no_of_selected_elements , & $ soln , & $ min_diff , $ sum , $ curr_sum , $ curr_position ) { if ( $ curr_position == $ n ) return ; if ( ( intval ( $ n / 2 ) - $ no_of_selected_elements ) > ( $ n - $ curr_position ) ) return ; TOWUtil ( $ arr , $ n , $ curr_elements , $ no_of_selected_elements , $ soln , $ min_diff , $ sum , $ curr_sum , $ curr_position + 1 ) ; $ no_of_selected_elements ++ ; $ curr_sum = ( $ curr_sum + $ arr [ $ curr_position ] ) ; $ curr_elements [ $ curr_position ] = true ; if ( $ no_of_selected_elements == intval ( $ n / 2 ) ) { if ( abs ( intval ( $ sum / 2 ) - $ curr_sum ) < $ min_diff ) { $ min_diff = abs ( intval ( $ sum / 2 ) - $ curr_sum ) ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) $ soln [ $ i ] = $ curr_elements [ $ i ] ; } } else { TOWUtil ( $ arr , $ n , $ curr_elements , $ no_of_selected_elements , $ soln , $ min_diff , $ sum , $ curr_sum , $ curr_position + 1 ) ; } $ curr_elements [ $ curr_position ] = false ; } function tugOfWar ( & $ arr , $ n ) { $ curr_elements = array_fill ( 0 , $ n , 0 ) ; $ soln = array_fill ( 0 , $ n , 0 ) ; $ min_diff = PHP_INT_MAX ; $ sum = 0 ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) { $ sum += $ arr [ $ i ] ; $ curr_elements [ $ i ] = $ soln [ $ i ] = false ; } TOWUtil ( $ arr , $ n , $ curr_elements , 0 , $ soln , $ min_diff , $ sum , 0 , 0 ) ; echo " The ▁ first ▁ subset ▁ is : ▁ " ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) { if ( $ soln [ $ i ] == true ) echo $ arr [ $ i ] . " ▁ " ; } echo " The second subset is : " for ( $ i = 0 ; $ i < $ n ; $ i ++ ) { if ( $ soln [ $ i ] == false ) echo $ arr [ $ i ] . " ▁ " ; } } $ arr = array ( 23 , 45 , -34 , 12 , 0 , 98 , -99 , 4 , 189 , -1 , 4 ) ; $ n = count ( $ arr ) ; tugOfWar ( $ arr , $ n ) ; ? >