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