# Tug of War of integers in a matrix using Backtracking Algorithm

Challenging Task: A set of 'n' integers are provided in an array. If 'n' is even it has to be divided into two unique arrays with n/2 elements each, else if 'n' is odd the matrix needs to be divided into two parts such that one part has 1 extra element as compared to the other. This division must occur in such a way that the difference between the sum of the integers in the divided parts must be as minimal as possible.

Solution:

For example, say the given matrix is: {3, 4, 5, -3, 100, 1, 89, 54, 23, 20}

It can be divided into  {4, 100, 1, 23, 20} and  {3, 5, -3, 89, 54} such that their difference between the sums is zero.

Such a division can be performed using Backtracking Algorithm paradigm where two empty lists of size n/2 or n/2+1 are created based on whether n is even or odd. Then each number is chosen in the main list and is placed appropriately in either one of the divided lists based on the satisfaction of our requirement.  This way, one element after the other are placed accordingly to achieve the final divided lists.

Following is the implementation for Tug of War problem. It prints the required arrays.

## C++ implementation to achieve tug of war results.

```#include <iostream>
#include <stdlib.h>
#include <limits.h>
using namespace std;

// function that tries every possible solution by calling itself recursively
void TOWUtil(int* arr, int n, bool* curr_elements, int no_of_selected_elements,
bool* soln, int* min_diff, int sum, int curr_sum, int curr_position)
{
// checks whether the it is going out of bound
if (curr_position == n)
return;

// checks that the numbers of elements left are not less than the
// number of elements required to form the solution
if ((n/2 - no_of_selected_elements) > (n - curr_position))
return;

// consider the cases when current element is not included in the solution
TOWUtil(arr, n, curr_elements, no_of_selected_elements,
soln, min_diff, sum, curr_sum, curr_position+1);

// add the current element to the solution
no_of_selected_elements++;
curr_sum = curr_sum + arr[curr_position];
curr_elements[curr_position] = true;

// checks if a solution is formed
if (no_of_selected_elements == n/2)
{
// checks if the solution formed is better than the best solution so far
if (abs(sum/2 - curr_sum) < *min_diff)
{
*min_diff = abs(sum/2 - curr_sum);
for (int i = 0; i<n; i++)
soln[i] = curr_elements[i];
}
}
else
{
// consider the cases where current element is included in the solution
TOWUtil(arr, n, curr_elements, no_of_selected_elements, soln,
min_diff, sum, curr_sum, curr_position+1);
}

// removes current element before returning to the caller of this function
curr_elements[curr_position] = false;
}

// main function that generate an arr
void tugOfWar(int *arr, int n)
{
// the boolen array that contains the inclusion and exclusion of an element
// in current set. The number excluded automatically form the other set
bool* curr_elements = new bool[n];

// The inclusion/exclusion array for final solution
bool* soln = new bool[n];

int min_diff = INT_MAX;

int sum = 0;
for (int i=0; i<n; i++)
{
sum += arr[i];
curr_elements[i] =  soln[i] = false;
}

// Find the solution using recursive function TOWUtil()
TOWUtil(arr, n, curr_elements, 0, soln, &min_diff, sum, 0, 0);

// Print the solution
cout << "The first subset is: ";
for (int i=0; i<n; i++)
{
if (soln[i] == true)
cout << arr[i] << " ";
}
cout << "\nThe second subset is: ";
for (int i=0; i<n; i++)
{
if (soln[i] == false)
cout << arr[i] << " ";
}
}

// Driver program to test above functions
int main()
{
int arr[] = {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4};
int n = sizeof(arr)/sizeof(arr[0]);
tugOfWar(arr, n);
return 0;
}
```

## Java implementation to achieve tug of war results.

```// Java program for Tug of war
import java.util.*;
import java.lang.*;
import java.io.*;

class TugOfWar
{
public int min_diff;

// function that tries every possible solution
// by calling itself recursively
void TOWUtil(int arr[], int n, boolean curr_elements[],
int no_of_selected_elements, boolean soln[],
int sum, int curr_sum, int curr_position)
{
// checks whether the it is going out of bound
if (curr_position == n)
return;

// checks that the numbers of elements left
// are not less than the number of elements
// required to form the solution
if ((n / 2 - no_of_selected_elements) >
(n - curr_position))
return;

// consider the cases when current element
// is not included in the solution
TOWUtil(arr, n, curr_elements,
no_of_selected_elements, soln, sum,
curr_sum, curr_position+1);

// add the current element to the solution
no_of_selected_elements++;
curr_sum = curr_sum + arr[curr_position];
curr_elements[curr_position] = true;

// checks if a solution is formed
if (no_of_selected_elements == n / 2)
{
// checks if the solution formed is
// better than the best solution so
// far
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
{
// consider the cases where current
// element is included in the
// solution
TOWUtil(arr, n, curr_elements,
no_of_selected_elements,
soln, sum, curr_sum,
curr_position + 1);
}

// removes current element before
// returning to the caller of this
// function
curr_elements[curr_position] = false;
}

// main function that generate an arr
void tugOfWar(int arr[])
{
int n = arr.length;

// the boolen array that contains the
// inclusion and exclusion of an element
// in current set. The number excluded
// automatically form the other set
boolean[] curr_elements = new boolean[n];

// The inclusion/exclusion array for
// final solution
boolean[] soln = new boolean[n];

min_diff = Integer.MAX_VALUE;

int sum = 0;
for (int i = 0; i < n; i++)
{
sum += arr[i];
curr_elements[i] = soln[i] = false;
}

// Find the solution using recursive
// function TOWUtil()
TOWUtil(arr, n, curr_elements, 0,
soln, sum, 0, 0);

// Print the solution
System.out.print("The first subset is: ");
for (int i = 0; i < n; i++)
{
if (soln[i] == true)
System.out.print(arr[i] + " ");
}
System.out.print("\nThe second subset is: ");
for (int i = 0; i < n; i++)
{
if (soln[i] == false)
System.out.print(arr[i] + " ");
}
}

// Driver program to test above functions
public static void main (String[] args)
{
int arr[] = {23, 45, -34, 12, 0, 98,
-99, 4, 189, -1, 4};
TugOfWar a = new TugOfWar();
a.tugOfWar(arr);
}
}

```

Output:

```The first subset is: 45 -34 12 98 -1
The second subset is: 23 0 -99 4 189 4```

POST A NEW COMMENT

• Input (stdin)

Output (stdout)

Input (stdin)

Expected Output

Compiler Message

Input (stdin)

`2    3`

`5`
`5`
`5`