Tug of war in C++

In this article, we will discuss Tug of war in C++ with examples.

One of the most well-known issues in computer science and mathematics is the tug of war. It is commonly referred to as the balance problem. In this task, we are taking a set of weights, and our objective is to split them into two groups as evenly as possible while minimizing the difference between the two groups' total weights. Follow the following steps to solve the tug of war problem:

• Divide a set of n integers into two subsets of size n/2 each, keeping the absolute difference between the two subsets as small as feasible. If n is odd, one subset's size must be (n-1)/2 and the second subset's size must be (n+1)/2. If n is even, both subset sizes must be strictly n/2.
• As an illustration, consider the following set: 3, 4, 5, -3, 100, 1, 89, 54, 23, 20. This set has a size of 10. This set should provide the outputs 4, 100, 1, 23, 20, and 3, 5, -3, 89, 54. The sum of the elements in both of the output subsets, which are both of size 5, is the same (148 and 148).
• Consider yet another instance when n is odd. Give the set the following values: 23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4. It is recommended that the output subsets be 45, -34, 12, 98, -1 and 23, 0, -99, 4, 189, 4. Elements in two subsets have sums of 120 and 121.
• The next approach attempts each potential half-size subset. The remaining items make up the other subset if just one subset of half the size is generated. We start with an empty set and piece it together one by one. Each element can either be a part of the current set, or it can be a part of the remaining elements (another subset). We take into account both scenarios for every constituent. We determine whether this solution is superior to the best one up until the size of the current set reaches n/2. If so, we revise the ideal solution.
• The solution to the problem of tug-of-war is given below. It outputs the necessary arrays.

Explanation:-

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

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

1. 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.
2. In this tug-of-war issue, we must examine every feasible subsequence that is half as large as the input array, and then the leftover components will form the other subsequence. Using the boolean array, we will take into account where each element is located within its respective subsequence. If the current subsequence's size is half that of the input array during the procedure, we must determine whether the optimal solution is accessible or not.

Steps of Algorithm:

Step 1: Make a function called "getResult()" that takes two parameters: a vector of integers for "input" and the size of that vector.

Step 2: Two boolean arrays called 'temp' and 'res', as well as two integer variables called 'mini' and 'sum', must be initialized in this 'getResult()' function.

Step 3: With the help of the 'i' variable, iterate using the for loop to assign the sum of all the input components to 'sum' and a 'false' value to both the boolean arrays 'temp' and 'res'.

Step 4: Create a function called "helper" that takes nine parameters: a vector of integers called "input", the vector's size. A boolean array called "temp", the number zero, which represents the total number of selected elements, a second boolean array called "res", the integer variable "mini", the integer variable "sum", the integer variable "curr_sum", and the integer variable "cur_Index + 1".

Step 5: In this "helper" function, the value of "selected" is increased, the value of the element at "cur_Index" of "input" is added to "cur_sum", and the element at "cur_Index" of "temp" is given the value "true".

Step 6: Check to see if the value of selected is equal to half the vector's size,

• If they are equal, the best course of action is to determine whether the absolute value of the difference between "sum / 2" and "curr_sum" is less than "mini", in which case the value should be assigned to "mini", and the entire temp array should be assigned to the "res" array using a for loop.
• If not, call the helper method repeatedly while modifying the parameters as indicated in the code.

Step 7: 'cur_Index' of the temp boolean array should be given the value 'false'.

Step 8: Print the entire sequence.

Program:

Let's take an example to demonstrate the tug of war in C++:

Output:

Complexity:

Time Complexity: O(2 ^ N)

In call to 'getResult()', we are also calling the 'helper' function, and in the helper function, we are checking all the valid options to make these 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, the overall space complexity will be O(N).

Benefits of Tug of war in C++:

The "Two-Pointer Technique" or "Two-Sum Problem", often known as tug of war, is a frequent algorithmic technique used in computer science and programming, particularly in C++ and comparable programming languages. It is a method for effectively resolving particular kinds of problems, not a feature or library in C++. The following are some advantages of applying the Tug of War method in C++:

1. Efficiency: When looking for matching pairs of items in an array or other data structures, the Tug of War technique is frequently employed to find solutions. With a temporal complexity of O(N), where N is the size of the input data, it can often be quite effective.
2. Optimization: When you need to identify the closest pair of items, two elements with a certain sum, or a way to divide an array into two subsets with the least amount of difference in their sums, this technique comes in extremely handy.
3. Memory Efficiency: Tug of war is a memory-efficient method of problem-solving since it often employs a fixed amount of memory for variables and pointers.
4. Simplicity: Simple implementation and application of the Tug of War technique in the C++ code are possible after we grasp its fundamental principles.
5. Versatility: A wide range of issues, including those involving arrays, linked lists, and other data structures, can be addressed by using this technique. It is not constrained to a particular data or issue domain.
6. Avoiding Nested Loops: Nested loops can be less effective and more difficult to manage in terms of code complexity; in some circumstances, employing Tug of War can assist you in avoiding using them.
7. Reduced Time Complexity: Tug of War can be used to convert some problems from having an O(N2) (quadratic time) time complexity to having an O(N) (linear time) time complexity, greatly enhancing the effectiveness of your methods.

Conclusion:

Although the Tug of War technique has numerous advantages, it's important to keep in mind that not all situations can be solved with it. Evaluate the current issue and decide whether this approach is suitable for your particular use case. Additionally, practice and expertise in algorithmic problem-solving may be necessary to master this strategy.