In tug of war problem, we have given an array of integers, divide the array into two subsets of size n/2 size each so that the difference of the sum of two subsets is as minimum as possible. If n is even each subset size is n/2. If n is odd one subset size must be n-1/2 and the size of another is n+1/2. The Sum of elements of both subsets should have approximately the same sum.

## Example

**Input **

arr[] = {1, 4, 7, -3, 15, 11, 14, 13, 10, 8}

**Output**

subset1: [4, 7, 8, 11, 13]

subset2: [10, 14, 6, 15, -3]

**Explanation**

Here, size is 10(even) each array should be of length 5

(4 + 7 + 8 + 11 + 13) – (10 + 14 + 6 + 15 + -3) = 0, minimum difference.

**Input **

arr[] = {-1, -3, -5, -6, 4, 11, 17, 23, 27, 19}

**Output**

subset1: [23, 17, -6, 4]

subset2: [27, -1, -3, 19, -5]

**Explanation**

Here, size is 9(odd),one array size is 5 and other will be 4.

(23 + 17 + -6 + 4) â€“ (27 + -1 + -3 + 19 + -5) = -1

## Algorithm of Tug of War

Try every subset of half size and compare it with the remaining half.

**a.** We initialize the current set as an empty set and add elements one by one.

**b.** For all the elements it should be part of the current set or part of the remaining set.

**c.** For the current set becomes n/2, we check whether this solution is better than the best solution available until that point.

**d.** Update if it is the best solution. Print the final solution.

## C++ Program of Tug of War

#include <iostream> #include <stdlib.h> #include <limits.h> using namespace std; void TugofWarRecur(int* array, int n, bool* current_elements, int selected_elements_count,bool* solution, int* min_diff, int sum, int current_sum, int current_position) { if (current_position == n) { return; } if ((n/2 - selected_elements_count) > (n - current_position)) { return; } TugofWarRecur(array, n, current_elements, selected_elements_count,solution, min_diff, sum, current_sum, current_position+1); selected_elements_count++; current_sum = current_sum + array[current_position]; current_elements[current_position] = true; if (selected_elements_count == n/2) { if (abs(sum/2 - current_sum) < *min_diff) { *min_diff = abs(sum/2 - current_sum); for (int i = 0; i<n; i++) { solution[i] = current_elements[i]; } } } else { TugofWarRecur(array, n, current_elements, selected_elements_count, solution, min_diff, sum, current_sum, current_position+1); } current_elements[current_position] = false; } void TugOfWar(int *array, int n) { bool* current_elements = new bool[n]; bool* solution = new bool[n]; int min_diff = INT_MAX; int sum = 0; for (int i=0; i<n; i++) { sum =sum + array[i]; current_elements[i] = solution[i] = false; } TugofWarRecur(array, n, current_elements, 0, solution, &min_diff, sum, 0, 0); cout << "subset 1: "; for (int i=0; i<n; i++) { if(solution[i] == true) { cout << array[i] << " "; } } cout << "\nsubset 2: "; for (int i=0; i<n; i++) { if(solution[i] == false) { cout << array[i] << " "; } } } //Main function int main() { int input_array[] = {1, 4, 7, -3, 15, 11, 14, 13, 10, 8}; int size = sizeof(input_array)/sizeof(input_array[0]); TugOfWar(input_array,size); return 0; }

subset 1: -3 11 14 10 8 subset 2: 1 4 7 15 13

## Complexity Analysis of Tug of War

**Time Complexity**

**O(n^2) **where n is the number of elements present in the array. If the size of subset n is even, it must be divided into n/2, but for the odd value of n, then the size of one subset must be (n-1)/2, and size of another subset must be (n+1)/2.

### Space Complexity

**O(1)** because we dont use any auxiliary space here.