## In the given 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 size of another is n+1/2. Sum of elements of both subsets should have approximately same sum.

### Example

**a)** Input array: [1, 4, 7, -3, 15, 11, 14, 13, 10, 8]

Output:

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

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

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.

**b)** Input array: [-1, -3, -5, -6, 4, 11, 17, 23, 27, 19]

Output:

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

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

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

**Time complexity: O(n^2)**

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

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

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

**c.** For 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

```
#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;
}
```