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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void TOWUtil ( int * arr , int n , bool * curr_elements , int no_of_selected_elements , bool * soln , int * min_diff , 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 , 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 == n / 2 ) { if ( abs ( sum / 2 - curr_sum ) < * min_diff ) { * min_diff = 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 , min_diff , sum , curr_sum , curr_position + 1 ) ; } curr_elements [ curr_position ] = false ; } void tugOfWar ( int * arr , int n ) { bool * curr_elements = new bool [ n ] ; bool * soln = new bool [ n ] ; int min_diff = INT_MAX ; 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 , & min_diff , sum , 0 , 0 ) ; cout << " The ▁ first ▁ subset ▁ is : ▁ " ; for ( int i = 0 ; i < n ; i ++ ) { if ( soln [ i ] == true ) cout << arr [ i ] << " ▁ " ; } cout << " The second subset is : " for ( int i = 0 ; i < n ; i ++ ) { if ( soln [ i ] == false ) cout << arr [ i ] << " ▁ " ; } } int main ( ) { int arr [ ] = { 23 , 45 , -34 , 12 , 0 , 98 , -99 , 4 , 189 , -1 , 4 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; tugOfWar ( arr , n ) ; return 0 ; }