Tug Of War

Introduction 

This blog will discuss the approach to solving the Tug off war problem. Before jumping into the approach to solving the tug of war problem, let’s first understand what is the tug of war problem, in this problem, we need to divide our array into two subsequences or we can say two subsets in such a way, that the difference between both the calculated sum of both the subsequence will be as minimum as possible.

Note: In this tug of war problem, if the size of the array is even, then, the size of the two subsequences will be half the size of the array, but if the size of the array is odd, then, the size of the first subsequence is the (size - 1) / 2 and the size of the second subsequence is the (size + 1) / 2.

Sample Example

Input:-

Output:- 

First subsequence

Second subsequence

Explanation:-

After checking each possible combination, the best-suited 2 subsequences are:

• 12 , 18 , 25
• 15, 10, 20, 8

The sum of all the elements of the first subsequence is 55, whereas the sum of the second subsequence is 53, and the difference between both the sums is only 2 which is the minimum, therefore these two are the resultant subsequences.

You can try this problem in Coding Ninjas Studio using this link.

Also see, Data Structures

Approach

In this tug of war problem, we have to check each possible subsequence of half the size of the input array, and, the other subsequence will be formed by the remaining elements. We will consider the position of each element in the respective subsequence using the boolean array. In the process, if the size of the current subsequence is equal to half the size of the input array, then, we have to check whether the best solution is available or not.

Steps of Algorithm

Step 1. Create a function ‘getResult()’ that will accept two parameters, i.e., one vector of integer ‘input’ and the second is the size of that vector.

Step 2. In this ‘getResult()’ function, we need to initialize two boolean arrays named ‘temp’ and ‘res’ and two integer variables named ‘mini’ and ‘sum’.

Step 3. Make an iteration using the ‘for’ loop with the help of the ‘i’ variable to assign the collective total of all the input elements to ‘sum’ and assign a ‘false’ value to both the boolean arrays ‘temp’ and ‘res’.

Step 4. Create a function ‘helper’ that will accept nine parameters, i.e., one vector of integer ‘input’, second is the size of the vector, third is the boolean array ‘temp’, fourth is the zero which will depict the total number of selected elements, the fifth is another boolean array ‘res’, sixth is the integer variable ‘mini’, seventh is the integer variable ‘sum’, eight is the integer variable ‘curr_sum’ and ninth is the integer variable ‘cur_Index + 1’

Step 5. In this ‘helper’ function, Increment the value of ‘selected’ and add the value of the element at ‘cur_Index’ of ‘input’ to ‘cur_sum’ and assign ‘true’ value to element at ‘cur_Index’ of ‘temp’.

Step 6. Check if the value of ‘selected’ is equal to half the value of the size of the vector or not,

• If it is equal then, check for the best solution by checking if the absolute value of the difference of ‘sum / 2’ and ‘curr_sum’ is less than ‘mini’ or not, if it is less than the value of ‘mini’, then assign that value to ‘mini’ and assign the complete ‘temp’ array to ‘res’ array using ‘for’ loop.
• Else, make a recursive call using the ‘helper’ function with updating the parameters as shown in the code.

Step 7. Assign ‘false’ value to the element at ‘cur_Index’ of ‘temp’ boolean array.

Step 8. Print both the subsequence.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

// Check all the valid options using this helper function
void helper(vector<int> input, int n, bool* temp, int selected, bool* res, int* mini, int sum, int curr_sum, int cur_Index)
{
   // Edge case
   if (cur_Index == n)
       return;

   // Check the size
   if ((n/2 - selected) > (n - cur_Index))
       return;

   // Case when current element is not considered in the result
   helper(input, n, temp, selected, res, mini, sum, curr_sum, cur_Index + 1);

   selected++;
   curr_sum = curr_sum + input[cur_Index];
   temp[cur_Index] = true;

   // checks if a solution is formed
   if (selected == n / 2)
   {
       // check for the best solution
       if (abs(sum / 2 - curr_sum) < *mini)
       {
           *mini = abs(sum/2 - curr_sum);
           for (int i = 0; i<n; i++)
               res[i] = temp[i];
       }
   }
   else
   {
       // Case when current element is considered in the result
       helper(input, n, temp, selected, res, mini, sum, curr_sum, cur_Index + 1);
   }

   temp[cur_Index] = false;
}

// main function that generate an arr
void getResult(vector<int> input, int n)
{
   bool* temp = new bool[n];

   bool* res = new bool[n];

   int mini = INT_MAX;

   int sum = 0;

   // Compute sum
   for (int i = 0; i < n; i++)
   {
       sum += input[i];
       temp[i] = res[i] = false;
   }

   // Recursive call to helper
   helper(input, n, temp, 0, res, &mini, sum, 0, 0);

   // Print both the subsequence
   cout << "The first subsequence: ";
   for (int i = 0; i<n; i++)
   {
       if (res[i] == true)
           cout << input[i] << ", ";
   }
   cout << endl;
   cout << "The second subsequence: ";
   for (int i = 0; i < n; i++)
   {
       if (res[i] == false)
           cout << input[i] << ", ";
   }
}

int main()
{
   // Input array
   vector<int> input = {15, 10, 20, 8, 12, 18, 25};
   int n = input.size();
   getResult(input, n);
   return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

The first subsequence: 12, 18, 25, 
The second subsequence: 15, 10, 20, 8,

Complexity Analysis

Time Complexity: O(2 ^ N)

Incall to ‘getResult()’, we are also calling the ‘helper’ function, and in the ‘helper’ function, we are checking all the valid options to make this two subsequences using a recursive call, therefore, the overall time complexity is O(2 ^ N).

Space Complexity: O(N)

As we are using ‘N’ extra space to store the binary tree, therefore, the overall space complexity will be O(N).

Check out this problem - 8 Queens Problem