Tug of War | Java program for 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 program to test above functions
import java . util . * ; import java . lang . * ; import java . io . * ; class TugOfWar { public int min_diff ; void TOWUtil ( int arr [ ] , int n , boolean curr_elements [ ] , int no_of_selected_elements , boolean soln [ ] , int sum , int curr_sum , int curr_position ) { if ( curr_position == n ) return ; if ( ( n / 2 - no_of_selected_elements ) > ( n - curr_position ) ) return ; TOWUtil ( arr , n , curr_elements , no_of_selected_elements , soln , 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 == n / 2 ) { if ( Math . abs ( sum / 2 - curr_sum ) < min_diff ) { min_diff = Math . abs ( sum / 2 - curr_sum ) ; for ( int i = 0 ; i < n ; i ++ ) soln [ i ] = curr_elements [ i ] ; } } else { TOWUtil ( arr , n , curr_elements , no_of_selected_elements , soln , sum , curr_sum , curr_position + 1 ) ; } curr_elements [ curr_position ] = false ; } void tugOfWar ( int arr [ ] ) { int n = arr . length ; boolean [ ] curr_elements = new boolean [ n ] ; boolean [ ] soln = new boolean [ n ] ; min_diff = Integer . MAX_VALUE ; int sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) { sum += arr [ i ] ; curr_elements [ i ] = soln [ i ] = false ; } TOWUtil ( arr , n , curr_elements , 0 , soln , sum , 0 , 0 ) ; System . out . print ( " The ▁ first ▁ subset ▁ is : ▁ " ) ; for ( int i = 0 ; i < n ; i ++ ) { if ( soln [ i ] == true ) System . out . print ( arr [ i ] + " ▁ " ) ; } System . out . print ( " The second subset is : "); for ( int i = 0 ; i < n ; i ++ ) { if ( soln [ i ] == false ) System . out . print ( arr [ i ] + " ▁ " ) ; } } public static void main ( String [ ] args ) { int arr [ ] = { 23 , 45 , - 34 , 12 , 0 , 98 , - 99 , 4 , 189 , - 1 , 4 } ; TugOfWar a = new TugOfWar ( ) ; a . tugOfWar ( arr ) ; } }