Tug of War | function that tries every possible 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
def TOWUtil ( arr , n , curr_elements , no_of_selected_elements , soln , min_diff , Sum , curr_sum , curr_position ) : NEW_LINE INDENT if ( curr_position == n ) : NEW_LINE INDENT return NEW_LINE DEDENT if ( ( int ( n / 2 ) - no_of_selected_elements ) > ( n - curr_position ) ) : NEW_LINE INDENT return NEW_LINE DEDENT TOWUtil ( arr , n , curr_elements , no_of_selected_elements , soln , min_diff , Sum , curr_sum , curr_position + 1 ) NEW_LINE no_of_selected_elements += 1 NEW_LINE curr_sum = curr_sum + arr [ curr_position ] NEW_LINE curr_elements [ curr_position ] = True NEW_LINE if ( no_of_selected_elements == int ( n / 2 ) ) : NEW_LINE INDENT if ( abs ( int ( Sum / 2 ) - curr_sum ) < min_diff [ 0 ] ) : NEW_LINE INDENT min_diff [ 0 ] = abs ( int ( Sum / 2 ) - curr_sum ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT soln [ i ] = curr_elements [ i ] NEW_LINE DEDENT DEDENT DEDENT else : NEW_LINE INDENT TOWUtil ( arr , n , curr_elements , no_of_selected_elements , soln , min_diff , Sum , curr_sum , curr_position + 1 ) NEW_LINE DEDENT curr_elements [ curr_position ] = False NEW_LINE DEDENT def tugOfWar ( arr , n ) : NEW_LINE INDENT curr_elements = [ None ] * n NEW_LINE soln = [ None ] * n NEW_LINE min_diff = [ 999999999999 ] NEW_LINE Sum = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT Sum += arr [ i ] NEW_LINE curr_elements [ i ] = soln [ i ] = False NEW_LINE DEDENT TOWUtil ( arr , n , curr_elements , 0 , soln , min_diff , Sum , 0 , 0 ) NEW_LINE print ( " The ▁ first ▁ subset ▁ is : ▁ " ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( soln [ i ] == True ) : NEW_LINE INDENT print ( arr [ i ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT print ( ) NEW_LINE print ( " The ▁ second ▁ subset ▁ is : ▁ " ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( soln [ i ] == False ) : NEW_LINE INDENT print ( arr [ i ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 23 , 45 , - 34 , 12 , 0 , 98 , - 99 , 4 , 189 , - 1 , 4 ] NEW_LINE n = len ( arr ) NEW_LINE tugOfWar ( arr , n ) NEW_LINE DEDENT