Tug of war - Arrange elements of array in two equal parts with same sum

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;
}
Try It


Next > < Prev
Scroll to Top