Tug of War

Problem Statement

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.

Input Format

The first and only one line containing an integer N.

Second-line containing N space-separated integer.

Output Format

First-line containing subset1 which have n/2 elements if n is even otherwise it has n-1/2 elements.

Second-line containing subset2 which have n/2 elements if n is even otherwise it has n+1/2 elements.

Constraints

• 1<=N<=10^3
• -10^5<=a[i]<=10^5

Example

10
1 4 7 -3 15 11 14 13 10 8

4 7 8 11 13
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.

9
-1 -3 -5 -6 4 17 23 27 19

-5 4 11 23 
-1 -3 -6 17 27

Explanation: Here, the size is 9(odd), one array size is 5 and the other will be 4. (23 + 11 + 4 + -5) – (27 + 17 + -6 + -3 + -1) = -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.

Implementation

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);
    for (int i=0; i<n; i++)
    {
        if(solution[i] == true)
        {
            cout << array[i] << " ";
        }
    }
    cout<<endl;
    for (int i=0; i<n; i++)
    {
        if(solution[i] == false)
        {
            cout << array[i] << " ";
        }
    }
}
 
//Main function
int main()
{
    int n;
    cin>>n;
    int input_array[n];
    for(int i=0;i<n;i++)
    {
        cin>>input_array[i];
    }
    TugOfWar(input_array,n);
    return 0;
}

import java.util.Scanner;
class sum
{
    public static void TOWUtil(int arr[], int n, boolean curr_elements[], int no_of_selected_elements, boolean soln[], int sum, int curr_sum, int curr_position, int min_diff) 
    { 
        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, sum, curr_sum, curr_position+1, min_diff); 
        no_of_selected_elements++; 
        curr_sum = curr_sum + arr[curr_position]; 
        curr_elements[curr_position] = true; 
        if (no_of_selected_elements == n / 2) 
        { 
            if (Math.abs(sum / 2 - curr_sum) < min_diff) 
            { 
                min_diff = Math.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, sum, curr_sum,curr_position + 1, min_diff); 
        } 
        curr_elements[curr_position] = false; 
    } 
    public static void solve(int arr[]) 
    { 
        int n = arr.length;
        boolean[] curr_elements = new boolean[n]; 
        boolean[] soln = new boolean[n]; 
        int min_diff = Integer.MAX_VALUE; 
        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, sum, 0, 0, min_diff); 
        for (int i = 0; i < n; i++) 
        { 
            if (soln[i] == true) 
                System.out.print(arr[i] + " "); 
        } 
        System.out.println(); 
        for (int i = 0; i < n; i++) 
        { 
            if (soln[i] == false) 
                System.out.print(arr[i] + " "); 
        }
        System.out.println();
    } 
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int input_array[] = new int [n];
        for(int i=0;i<n;i++)
        {
            input_array[i] = sr.nextInt();
        }
        solve(input_array);
    }
}

6
9 6 4 2 7 -2

9 6 4 
2 7 -2