# Design Python Program for Tug of War

In this tutorial, you will learn to design a Python program for the Tug of War.

## Python Program for Tug of War

In this problem, we are provided with a set of integers. We then need to break the given set into two different sets in such a way that there is a minimum difference in the sum of two subsets. That is we divide the team into two groups with equal strengths to participate in-game.

Consider total number of people (set) is N.

If N is even – Size of each team = N/2

If N is odd – Size of one team = (N-1)/2 while other contains (N+1)/2

Let us consider a small example :

1 )

Given set = {3, 4, 5, -3, 100, 1, 89, 54, 23, 20}

Here, N= 10 (Even)

Thus team 1 = {4, 100, 1, 23, 20}; Sum = 148

Team 2 = {3, 5, -3, 89, 54}; Sum = 148

2)

Given set = {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4}

Here, N= 11 (Odd)

Thus team 1 = {45, -34, 12, 98, -1} ; Sum = 120

Team 2 = {23, 0, -99, 4, 189, 4}; Sum = 121

Algorithm :

```Begin
if position = n, then
return
if (n/2-selected) > (n - position), then
return
TugOfWar(weight, n, current, selected, solution, difference, sum, total, position+1)
selected := selected + 1
total := total + weight[position]
current[position] := true

if selected = n/2, then
if difference of (sum/2 and total) < diff, then
difference := difference of (sum/2 and total)
for i := 0 to n, do
solution[i] := current[i]
done
else
TugOfWar(weight, n, current, selected, solution, difference, sum, total, position+1)
current[position] := false
End```
1. Initialize the current set as empty. Now there are two solutions for every element, either it will be in the current set or else another subset.
2. Considering both possibilities, when current set is full(ie contains N/2 elements) check if it best solution out of all previous solution.
3. If yes, update the else discard.

Here is a sample code :

```def TOW_Until(array, n, curr_elements, no_of_selected_elements,soln, min_diff, Sum, curr_sum, curr_position):

if (curr_position == n):
return
if ((int(n / 2) - no_of_selected_elements) > (n - curr_position)):
return
TOW_Until(array, n, curr_elements, no_of_selected_elements, soln, min_diff, Sum, curr_sum, curr_position + 1)

no_of_selected_elements += 1
curr_sum = curr_sum + array[curr_position]
curr_elements[curr_position] = True

if (no_of_selected_elements == int(n / 2)):

if (abs(int(Sum / 2) - curr_sum) < min_diff[0]):
min_diff[0] = abs(int(Sum / 2) - curr_sum)
for i in range(n):
soln[i] = curr_elements[i]
else:
TOW_Until(array, n, curr_elements, no_of_selected_elements, soln, min_diff, Sum, curr_sum, curr_position + 1)

curr_elements[curr_position] = False

def tugOfWar(array, n):
curr_elements = [None] * n

soln = [None] * n

min_diff = [999999999999]

Sum = 0
for i in range(n):
Sum += array[i]
curr_elements[i] = soln[i] = False

TOW_Until(array, n, curr_elements, 0, soln, min_diff, Sum, 0, 0)

print("First subset: ")
for i in range(n):
if (soln[i] == True):
print(array[i], end = " ")
print()
print("Second subset: ")
for i in range(n):
if (soln[i] == False):
print(array[i], end = " ")
if __name__ == '__main__':

array = [3, 4, 5, -3, 100, 1, 89, 54, 23, 20]
n = len(array)
tugOfWar(array, n)

```

OUTPUT :

```First subset:
4 100 1 23 20
Second subset:
3 5 -3 89 54```

You may also like :