Tug of War in Java

As in the tug-of-war issue, we must divide the given collection of n numbers into two groups of sizes that are equal or nearly equivalent. A minimum difference must exist between the sum of the numbers included in the initial subset and, thus, the following subset when the supplied set is subdivided. The length of each collection must equal n / 2 if n is an even number. The size of one group must be n / 2, and the length of the other set must be (n + 1) / 2 if somehow the value of n is odd. Let's break it down with the aid of some examples.

Problem:

• An array of n numerals is supplied to you.
• You must split up these n numerals into two subgroups so that the difference between the two subsets' sums is as small as possible.
• Both sets will have precisely n/2 elements if n is even. One set will have (n-1)/2, and the second set will include (n+1)/2 pieces if n is an odd number.
• If the division is not feasible, print "-1."
• By using the input array [a, b, c, d] to clarify this query,

Example 1:

S is a set of 10 elements that has the following values: 3, 5, 4, 3, 1, 100, 54, 89, 20, 23.

Undoubtedly, 10 is an even integer. As a result, the two subsets we will extract from the supplied set must each be of average size (10 / 2 = 5). They are these two subsets:

S1 = {4, 1, 100, 20, 23} as well as S2 = {-3, 5, 3, 54, 89}

The subset S1 adds up to 4 + 1 + 100 + 20 + 23 which equals 148.

The subset S2 has the following sum: - 3 + 5 + 3 + 54 + 89 = 148.

As a result, we can see that the summation of subsets S1 and S2 are equal. As a result, the minimum difference between the two groups is 148 - 148 = 0.

Example 2:

The set S has the following values: -34, 23, 98, 45, 12, 4, 4, -99, -1, 189, 0, and so forth.

Undoubtedly, 11 is an odd integer. This means that the two subsets we will extract from the supplied set must have sizes of 5 (10 / 2 = 5) and 6 (10 / 5 + 1 = 6). They are these two subsets:

S1 = {45, -34, 12, 98, -1} as well as S2 = {23, 4, 4, -99, 189, 0}

Subset S1 adds up to 45 -34 + 12 + 98 -1 = 120.

The subset S2 is equal to 23 + 4 + 4 -99 + 189 + 0 = 121 as a whole.

As a result, we can see that the summation of subsets S1 and S2 are equal. Thus, 121 – 120 = 1 represents the difference between the two subsets. We are unable to get a difference of less than one if we create any additional pair of equal-sized subsets. The most negligible difference that can exist for the specific set is 1, thus.

Approach

The following solution searches for every single half-size subgroup conceivable. If the first subset is half the size, the remaining components form a second subset. The current set is created with no elements and is then filled. Including an entity in the current set is one option, and excluding an item from the current batch is the other. We fill all subsets by taking these two alternatives into account.

The next approach attempts each potential half-size subset. The remaining items make up the other subset if just one subgroup of half the size is generated. We start off with an empty set and piece it together one by one. Every element has two potential outcomes: either a part of the present set or a portion of the leftover elements (remaining subgroups). 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 will revise the ideal solution.

Implementation

Check out how the abovementioned strategy is used to solve the tug-of-war problem.

Tugofwar.java

// Importing the required packages 
import java.io.*;
public class Tugofwar  
{  
public int min;  
  
// a utility function that repeatedly calls itself to try 
// every potential resolution 
void toutil(int arr[], int s, boolean ele[],  
int selected, boolean ans[],  
int add, int presum, int pos)  
{  
// determining if the position is approaching the bounds  
if (pos == s)  
{  
return;  
}  
  
// ensuring that the remaining element counts are at least
// as many as the components needed to build the solution  
if ((s / 2 - selected) > (s - pos))  
{  
return;  
}  
  
// Think about the scenarios where the present component 
// isn't used in the solution. 
toutil(arr, s, ele,   
selected, ans,   
add, presum, pos + 1);  
  
// adding the current element to our current solution 
// in the following steps.
selected = selected + 1;  
presum = presum + arr[pos];  
ele[pos] = true;  
  
//verifying if we have successfully made the solution or not 
if (selected == s / 2)  
{  
// determining whether the developed solution is superior 
// to the best one thus far 
if (Math.abs(add / 2 - presum) < min)  
{  
min = Math.abs(add / 2 - presum);  
for (int j = 0; j < s; j++)  
{  
ans[j] = ele[j];  
}  
}  
}  
else  
{  
// the current component of the solution is included in the subsequent 
// recursive call.  
toutil(arr, s, ele,  
selected,  
ans, add, presum,  
pos + 1);  
}  
  
// In order to return to the 
// user of this method, the current 
// element is removed. 
ele[pos] = false;  
}    
void tow(int arr[])  
{  
int s = arr.length;  
  
// the boolean integer that contains whether an element 
// is included in the current set or not. The quantity
// that is automatically subtracted from the other set 
boolean[] ele = new boolean[s];  
  
// The inclusion/exclusion array for  
// final solution  
boolean[] ans = new boolean[s];  
  
min = Integer.MAX_VALUE;  
  
int add = 0;  
for (int j = 0; j < s; j++)  
{  
add = add + arr[j];  
ele[j] = ans[j] = false;  
}  
  
// Finding the answer using the recursion
// calling the function toutil recursively.  
toutil(arr, s, ele, 0,  
ans, add, 0, 0);  
  
// Printing the solution 
System.out.print("Elements that make the first subset are : ");  
for (int j = 0; j < s; j++)  
{  
if (ans[j] == true)  
{  
System.out.print(arr[j] + " ");  
}  
}  
  
System.out.print("\n");  
System.out.print("Elements that make the Second subset are : ");  
for (int j = 0; j < s; j++)  
{  
if (ans[j] == false)  
{  
System.out.print(arr[j] + " ");  
}  
}  
}  
  
// Main method starts here
public static void main (String[] args)  
{  
// Making the input array  
int arr[] = new int[]{-34, 23, 98, 45, 12, 4, 4, -99, -1, 189, 0};  
  
// finding the length of the array
int s = arr.length;   
  
// Object creation for the class Tugofwar             
Tugofwar obj = new Tugofwar();  
  
System.out.println("Taken array is as follows : ");  
for(int i = 0; i < s; i++)  
{  
System.out.print(arr[i] + " ");  
}  
  
System.out.println();  
  
// Calling the method tow() using the object    
obj.tow(arr);  
  
// Changing the array taken as input  
arr = new int[]{-3, 5, 4, 3, 1, 100, 54, 89, 20, 23};  
  
// finding the length of the updated array   
s = arr.length;  
  
System.out.println("\n");  
  
System.out.println("Updated array is as follows : ");  
for(int i = 0; i < s; i++)  
{  
System.out.print(arr[i] + " ");  
}  
  
System.out.println();  
  
// Calling the method tow() using the object    
obj.tow(arr);  
}  
}  

Output:

Taken array is as follows :
-34 23 98 45 12 4 4 -99 -1 189 0
Elements that make the First subset are : -34 98 45 12 -1
Elements that make the Second subset are : 23 4 4 -99 189 0


Updated array is as follows :
-3 5 4 3 1 100 54 89 20 23
Elements that make the First subset are : 4 1 100 20 23
Elements that make the Second subset are : -3 5 3 54 89
 

Time Complexity:

The above program has a time complexity of 2n, and wherein n represents the length of the array that is a number of elements.