Tug Of War

Harsh Goyal
Last Updated: May 13, 2022

Introduction 

This blog will discuss the approach to solve the Tug of 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 in two subsequence 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 subsequence 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:-

15

10

20

8

12

18

25

 

Output:- 

First subsequence

12

18

25

Second subsequence

15

10

20

8

 

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 codestudio using this link.

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

 

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 ‘helper’ function, and in ‘helper’ function, we are checking all the valid options to make these two subsequence 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).

Frequently asked questions

Q1) What is the subsequence?

Ans. subsequence is also a type of array which is contiguous and is usually a small section of the bigger array.

 

Q2) What is a boolean array?

Ans. The array in which the value of elements could be true or false only is a boolean array. 

 

Q3) Difference b/w recursion and backtracking?

Ans. Recursion and Backtracking both are nearly similar because both call their own function again and again, but the only difference between both of them is that in recursion, the function calls stops when it satisfies the base case, whereas, in backtracking, recursion is used to check and find all possible combinations until and unless we get the best solution for that problem.

Key takeaways

In this article, we discussed the What is Tug of war, discussed the various approaches to solving this problem programmatically, the time and space complexities, and how to optimize the approach by reducing the space complexity of the problem. 

If you think that this blog helped you share it with your friends!. Refer to the DSA C++ course for more information.

Until then, All the best for your future endeavors, and Keep Coding.

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think