Posted on by Kalkicode
Code Backtracking

Tug of War

Tug of War is a problem in computer science that involves dividing a set of numbers into two subsets such that the difference between the sums of the subsets is minimized. This problem can be solved using the concept of recursion and backtracking. The goal is to find two subsets whose sums are as close as possible to each other.

Problem Statement and Explanation

Given an array of numbers, the task is to divide the array into two subsets such that the difference between the sums of the subsets is minimized. Let's consider an example to better understand the problem:

Consider the array: [6, 8, 35, -24, 62, 82, 13, 56, 32]. We need to divide this array into two subsets, A and B. The subsets should be such that the difference between the sums of A and B is minimized.

The expected output for the given array is: 

    Total Sum: 270
    Set A: [6, 35, -24, 62, 56] (Sum: 135)
    Set B: [8, 82, 13, 32] (Sum: 135)

In this example, both sets have a sum of 135, and the difference between the sums is minimized.

Pseudocode Algorithm

The following pseudocode explains the algorithm to solve the Tug of War problem: 

    function printArray(arr, size):
        for i = 0 to size-1:
            print arr[i]

    function getDifference(a, b):
        if a > b:
            return a - b
        else:
            return b - a

    function subset(arr, visit, result, n, sum, i, j, k, difference):
        if j == n/2 or i == n or visit[i] != 0 or difference == 0:
            return

        subset(arr, visit, result, n, sum, i+1, j, k, difference)

        visit[i] = 1

        if j == (n/2) - 1:
            if getDifference(sum/2, k + arr[i]) < difference:
                difference = getDifference(sum/2, k + arr[i])
                for l = 0 to n-1:
                    result[l] = visit[l]

        subset(arr, visit, result, n, sum, i+1, j+1, k+arr[i], difference)
        visit[i] = 0

    function tugOfWar(arr, n):
        if n <= 1:
            return

        visit[n]
        result[n]
        sum = 0

        for i = 0 to n-1:
            visit[i] = 0
            result[i] = 0
            sum = sum + arr[i]

        difference = INT_MAX
        subset(arr, visit, result, n, sum, 0, 0, 0, difference)

        printArray(arr, n)
        print "Total Sum:", sum

        sum = 0
        for i = 0 to n-1:
            if result[i] == 0:
                print arr[i]
                sum = sum + arr[i]

        print "Set A Sum:", sum

        sum = 0
        for i = 0 to n-1:
            if result[i] == 1:
                print arr[i]
                sum = sum + arr[i]

        print "Set B Sum:", sum

Code Solution

// C Program 
// Tug of War

#include <stdio.h>
#include <limits.h> //for INT_MAX

//Display elements of given array
void printArray(int arr[], int size)
{
    for (int i = 0; i < size; ++i)
    {
        printf("  %d", arr[i]);
    }
    printf("\n");
}

// Returns the difference of two numbers
int getDifference(int a,int b)
{
    if(a > b)
    {
        return a-b;
    }
    else
    {
        return b-a;
    }
}

// Find two subsets of minimum difference
void subset(int arr[],
    int visit[], 
    int result[], 
    int n, 
    int sum, 
    int i, 
    int j,
    int k,
    int *difference)
{

    if(j == n/2 || i == n || visit[i] != 0 || *difference == 0)
    {
        // When result are found or no need to visit current element
        return;
    }
    // Visit to next element through by recursion
    subset(arr,visit,result,n,sum,i+1,j, k,difference);

    // Set current element are active (used)
    visit[i] = 1;
    
    if(j==(n/2)-1)
    {
        if(getDifference(sum/2 , k+arr[i]) < *difference)
        {
            // When a new minimum difference is obtained
            *difference = getDifference(sum/2 , k+arr[i]);

            // Get the new result
            for (int l = 0; l < n; ++l)
            {
               result[l] = visit[l];
            }
        }
    }
    // Visit to next element through by recursion
    subset(arr,visit,result,n,sum,i+1,j+1,k+arr[i],difference);

    // Change status of visited element
    visit[i] = 0;
}

// Handles the request to find subset of minimum sum
void tugOfWar(int arr[],int n)
{

    if(n <= 1)
    {
        return;
    }
    // Loop controlling variable
    int i = 0;

    // This are used to find subset result
    int visit[n];
    int result[n];

    // Initialize current sum
    int sum = 0;

    for (i = 0; i < n; ++i)
    {
        visit[i] = 0;

        result[i] = 0;
        
        sum = sum + arr[i];
    }

    int difference = INT_MAX;

    // Find subset
    subset(arr,visit,result,n,sum,0,0, 0,&difference);
 
	printArray(arr,n);
    // Display the calculated total sum
    printf("  Total Sum : %d \n",sum);
    // Reset the sum value
    sum = 0;
    // Display elements of first set A
    for (i = 0; i < n; ++i)
    {
        if(result[i]==0)
        {
            printf("  %d",arr[i]);
            sum = sum + arr[i];
        }
    }
    // Display the sum of set A
    printf("\n  Set A Sum : %d \n",sum);
    // Reset the sum value
    sum = 0;
    // Display elements of first set B
    for (i = 0; i < n; ++i)
    {
        if(result[i]==1)
        {
            printf("  %d",arr[i]);
            sum = sum + arr[i];
        }
    }
    // Display the sum of set B
    printf("\n  Set B Sum : %d\n",sum);
}


int main(int argc, char const *argv[])
{
    // Define array of integer elements
    int arr[] = {6,8,35,-24,62,82,13,56,32};

    // Get the size
    int n = sizeof(arr)/sizeof(arr[0]);

    tugOfWar(arr,n);

    return 0;
}

Output

  6  8  35  -24  62  82  13  56  32
  Total Sum : 270
  6  35  -24  62  56
  Set A Sum : 135
  8  82  13  32
  Set B Sum : 135
/*
  Java Program for
  Tug of War 
*/
class TugOfWar
{
	public int difference;
	public TugOfWar()
	{
		this.difference = Integer.MAX_VALUE;
	}
	//Display elements of given array
	public void printArray(int[] arr, int size)
	{
		for (int i = 0; i < size; ++i)
		{
			System.out.print("  " + arr[i]);
		}
		System.out.print("\n");
	}
	// Returns the difference of two numbers
	public int getDifference(int a, int b)
	{
		if (a > b)
		{
			return a - b;
		}
		else
		{
			return b - a;
		}
	}
	// Find two subsets of minimum difference
	public void subset(int[] arr, boolean[] visit, boolean[] result, int n, int sum, int i, int j, int k)
	{
		if (j == n / 2 || i == n || visit[i] == true || this.difference == 0)
		{
			// When result are found or no need to visit current element
			return;
		}
		// Visit to next element through by recursion
		subset(arr, visit, result, n, sum, i + 1, j, k);
		// Set current element are active (used)
		visit[i] = true;
		if (j == (n / 2) - 1)
		{
			if (getDifference(sum / 2, k + arr[i]) < this.difference)
			{
				// When a new minimum difference is obtained
				this.difference = getDifference(sum / 2, k + arr[i]);
				// Get the new result
				for (int l = 0; l < n; ++l)
				{
					result[l] = visit[l];
				}
			}
		}
		// Visit to next element through by recursion
		subset(arr, visit, result, n, sum, i + 1, j + 1, k + arr[i]);
		// Change status of visited element
		visit[i] = false;
	}
	// Handles the request to find subset of minimum sum
	public void tugOfWar(int[] arr, int n)
	{
		if (n <= 1)
		{
			return;
		}
		// Loop controlling variable
		int i = 0;
		// This are used to find subset result
		boolean[] visit = new boolean[n];
		boolean[] result = new boolean[n];
		// Initialize current sum
		int sum = 0;
		for (i = 0; i < n; ++i)
		{
			visit[i] = false;
			result[i] = false;
			sum = sum + arr[i];
		}
		this.difference = Integer.MAX_VALUE;
		// Find subset
		subset(arr, visit, result, n, sum, 0, 0, 0);
		// Reset the sum value
		
		printArray(arr, n);
		// Display the calculated total sum
		System.out.print("  Total Sum : " + sum + " \n");
		// Reset the sum value
      	sum = 0;
      
        // Display elements of first set A
		for (i = 0; i < n; ++i)
		{
			if (result[i] == false)
			{
				System.out.print("  " + arr[i]);
				sum = sum + arr[i];
			}
		}
		// Display the sum of set A
		System.out.print("\n  Set A Sum : " + sum + " \n");
		// Reset the sum value
		sum = 0;
		// Display elements of first set B
		for (i = 0; i < n; ++i)
		{
			if (result[i] == true)
			{
				System.out.print("  " + arr[i]);
				sum = sum + arr[i];
			}
		}
		// Display the sum of set B
		System.out.print("\n  Set B Sum : " + sum + "\n");
	}
	public static void main(String[] args)
	{
		TugOfWar task = new TugOfWar();
		// Define array of integer elements
		int[] arr = {
			6 , 8 , 35 , -24 , 62 , 82 , 13 , 56 , 32
		};
		// Get the size
		int n = arr.length;
		task.tugOfWar(arr, n);
	}
}

Output

  6  8  35  -24  62  82  13  56  32
  Total Sum : 270
  6  35  -24  62  56
  Set A Sum : 135
  8  82  13  32
  Set B Sum : 135
// Include header file
#include <iostream>
#include<limits.h>
using namespace std;
/*
  C++ Program for
  Tug of War 
*/
class TugOfWar
{
	public: int difference;
	TugOfWar()
	{
		this->difference = INT_MAX;
	}
	//Display elements of given array
	void printArray(int arr[], int size)
	{
		for (int i = 0; i < size; ++i)
		{
			cout << "  " << arr[i];
		}
		cout << "\n";
	}
	// Returns the difference of two numbers
	int getDifference(int a, int b)
	{
		if (a > b)
		{
			return a - b;
		}
		else
		{
			return b - a;
		}
	}
	// Find two subsets of minimum difference
	void subset(int arr[], bool visit[], bool result[], int n, int sum, int i, int j, int k)
	{
		// When result are found or no need to visit current element
		if (j == n / 2 || i == n || visit[i] == true || this->difference == 0)
		{
			return;
		}
		// Visit to next element through by recursion
		this->subset(arr, visit, result, n, sum, i + 1, j, k);
		// Set current element are active (used)
		visit[i] = true;
		if (j == (n / 2) - 1)
		{
			if (this->getDifference(sum / 2, k + arr[i]) < this->difference)
			{
				// When a new minimum difference is obtained
				this->difference = this->getDifference(sum / 2, k + arr[i]);
				// Get the new result
				for (int l = 0; l < n; ++l)
				{
					result[l] = visit[l];
				}
			}
		}
		// Visit to next element through by recursion
		this->subset(arr, visit, result, n, sum, i + 1, j + 1, k + arr[i]);
		// Change status of visited element
		visit[i] = false;
	}
	// Handles the request to find subset of minimum sum
	void tugOfWar(int arr[], int n)
	{
		if (n <= 1)
		{
			return;
		}
		// Loop controlling variable
		int i = 0;
		// This are used to find subset result
		bool visit[n];
		bool result[n];
		// Initialize current sum
		int sum = 0;
		for (i = 0; i < n; ++i)
		{
			visit[i] = false;
			result[i] = false;
			sum = sum + arr[i];
		}
		this->difference = INT_MAX;
		// Find subset
		this->subset(arr, visit, result, n, sum, 0, 0, 0);
		// Reset the sum value
		this->printArray(arr, n);
		// Display the calculated total sum
		cout << "  Total Sum : " << sum << " \n";
		// Reset the sum value
		sum = 0;
		// Display elements of first set A
		for (i = 0; i < n; ++i)
		{
			if (result[i] == false)
			{
				cout << "  " << arr[i];
				sum = sum + arr[i];
			}
		}
		// Display the sum of set A
		cout << "\n  Set A Sum : " << sum << " \n";
		// Reset the sum value
		sum = 0;
		// Display elements of first set B
		for (i = 0; i < n; ++i)
		{
			if (result[i] == true)
			{
				cout << "  " << arr[i];
				sum = sum + arr[i];
			}
		}
		// Display the sum of set B
		cout << "\n  Set B Sum : " << sum << "\n";
	}
};
int main()
{
	TugOfWar task = TugOfWar();
	// Define array of integer elements
	int arr[] = {
		6 , 8 , 35 , -24 , 62 , 82 , 13 , 56 , 32
	};
	// Get the size
	int n = sizeof(arr) / sizeof(arr[0]);
	task.tugOfWar(arr, n);
	return 0;
}

Output

  6  8  35  -24  62  82  13  56  32
  Total Sum : 270
  6  35  -24  62  56
  Set A Sum : 135
  8  82  13  32
  Set B Sum : 135
// Include namespace system
using System;
/*
  C# Program for
  Tug of War 
*/
public class TugOfWar
{
	public int difference;
	public TugOfWar()
	{
		this.difference = int.MaxValue;
	}
	//Display elements of given array
	public void printArray(int[] arr, int size)
	{
		for (int i = 0; i < size; ++i)
		{
			Console.Write("  " + arr[i]);
		}
		Console.Write("\n");
	}
	// Returns the difference of two numbers
	public int getDifference(int a, int b)
	{
		if (a > b)
		{
			return a - b;
		}
		else
		{
			return b - a;
		}
	}
	// Find two subsets of minimum difference
	public void subset(int[] arr, Boolean[] visit, Boolean[] result, int n, int sum, int i, int j, int k)
	{
		// When result are found or no need to visit current element
		if (j == n / 2 || i == n || visit[i] == true || this.difference == 0)
		{
			return;
		}
		// Visit to next element through by recursion
		subset(arr, visit, result, n, sum, i + 1, j, k);
		// Set current element are active (used)
		visit[i] = true;
		if (j == (n / 2) - 1)
		{
			if (getDifference(sum / 2, k + arr[i]) < this.difference)
			{
				// When a new minimum difference is obtained
				this.difference = getDifference(sum / 2, k + arr[i]);
				// Get the new result
				for (int l = 0; l < n; ++l)
				{
					result[l] = visit[l];
				}
			}
		}
		// Visit to next element through by recursion
		subset(arr, visit, result, n, sum, i + 1, j + 1, k + arr[i]);
		// Change status of visited element
		visit[i] = false;
	}
	// Handles the request to find subset of minimum sum
	public void tugOfWar(int[] arr, int n)
	{
		if (n <= 1)
		{
			return;
		}
		// Loop controlling variable
		int i = 0;
		// This are used to find subset result
		Boolean[] visit = new Boolean[n];
		Boolean[] result = new Boolean[n];
		// Initialize current sum
		int sum = 0;
		for (i = 0; i < n; ++i)
		{
			visit[i] = false;
			result[i] = false;
			sum = sum + arr[i];
		}
		this.difference = int.MaxValue;
		// Find subset
		subset(arr, visit, result, n, sum, 0, 0, 0);
		// Reset the sum value
		printArray(arr, n);
		// Display the calculated total sum
		Console.Write("  Total Sum : " + sum + " \n");
		// Reset the sum value
		sum = 0;
		// Display elements of first set A
		for (i = 0; i < n; ++i)
		{
			if (result[i] == false)
			{
				Console.Write("  " + arr[i]);
				sum = sum + arr[i];
			}
		}
		// Display the sum of set A
		Console.Write("\n  Set A Sum : " + sum + " \n");
		// Reset the sum value
		sum = 0;
		// Display elements of first set B
		for (i = 0; i < n; ++i)
		{
			if (result[i] == true)
			{
				Console.Write("  " + arr[i]);
				sum = sum + arr[i];
			}
		}
		// Display the sum of set B
		Console.Write("\n  Set B Sum : " + sum + "\n");
	}
	public static void Main(String[] args)
	{
		TugOfWar task = new TugOfWar();
		// Define array of integer elements
		int[] arr = {
			6 , 8 , 35 , -24 , 62 , 82 , 13 , 56 , 32
		};
		// Get the size
		int n = arr.Length;
		task.tugOfWar(arr, n);
	}
}

Output

  6  8  35  -24  62  82  13  56  32
  Total Sum : 270
  6  35  -24  62  56
  Set A Sum : 135
  8  82  13  32
  Set B Sum : 135
<?php
/*
  Php Program for
  Tug of War 
*/
class TugOfWar
{
	public $difference;

	function __construct()
	{
		$this->difference = PHP_INT_MAX;
	}
	//Display elements of given array
	public	function printArray( & $arr, $size)
	{
		for ($i = 0; $i < $size; ++$i)
		{
			echo "  ". $arr[$i];
		}
		echo "\n";
	}
	// Returns the difference of two numbers
	public	function getDifference($a, $b)
	{
		if ($a > $b)
		{
			return $a - $b;
		}
		else
		{
			return $b - $a;
		}
	}
	// Find two subsets of minimum difference
	public	function subset( & $arr, & $visit, & $result, $n, $sum, $i, $j, $k)
	{
		// When result are found or no need to visit current element
		if ($j == intval($n / 2) || $i == $n || $visit[$i] == true || $this->difference == 0)
		{
			return;
		}
		// Visit to next element through by recursion
		$this->subset($arr, $visit, $result, $n, $sum, $i + 1, $j, $k);
		// Set current element are active (used)
		$visit[$i] = true;
		if ($j == (intval($n / 2)) - 1)
		{
			if ($this->getDifference(intval($sum / 2), $k + $arr[$i]) < $this->difference)
			{
				// When a new minimum difference is obtained
				$this->difference = $this->getDifference(intval($sum / 2), $k + $arr[$i]);
				// Get the new result
				for ($l = 0; $l < $n; ++$l)
				{
					$result[$l] = $visit[$l];
				}
			}
		}
		// Visit to next element through by recursion
		$this->subset($arr, $visit, $result, $n, $sum, $i + 1, $j + 1, $k + $arr[$i]);
		// Change status of visited element
		$visit[$i] = false;
	}
	// Handles the request to find subset of minimum sum
	public	function tugOfWar( & $arr, $n)
	{
		if ($n <= 1)
		{
			return;
		}
		// Loop controlling variable
		$i = 0;
		// This are used to find subset result
		$visit = array_fill(0, $n, false);
		$result = array_fill(0, $n, false);
		// Initialize current sum
		$sum = 0;
		for ($i = 0; $i < $n; ++$i)
		{
			$sum = $sum + $arr[$i];
		}
		$this->printArray($arr, $n);
		// Display the calculated total sum
		echo "  Total Sum : ". $sum ." \n";
		$this->difference = PHP_INT_MAX;
		// Find subset
		$this->subset($arr, $visit, $result, $n, $sum, 0, 0, 0);
		// Reset the sum value
		// Reset the sum value
		$sum = 0;
		// Display elements of first set A
		for ($i = 0; $i < $n; ++$i)
		{
			if ($result[$i] == false)
			{
				echo "  ". $arr[$i];
				$sum = $sum + $arr[$i];
			}
		}
		// Display the sum of set A
		echo "\n  Set A Sum : ". $sum ." \n";
		// Reset the sum value
		$sum = 0;
		// Display elements of first set B
		for ($i = 0; $i < $n; ++$i)
		{
			if ($result[$i] == true)
			{
				echo "  ". $arr[$i];
				$sum = $sum + $arr[$i];
			}
		}
		// Display the sum of set B
		echo "\n  Set B Sum : ". $sum ."\n";
	}
}

function main()
{
	$task = new TugOfWar();
	// Define array of integer elements
	$arr = array(6, 8, 35, -24, 62, 82, 13, 56, 32);
	// Get the size
	$n = count($arr);
	$task->tugOfWar($arr, $n);
}
main();

Output

  6  8  35  -24  62  82  13  56  32
  Total Sum : 270
  6  35  -24  62  56
  Set A Sum : 135
  8  82  13  32
  Set B Sum : 135
/*
  Node Js Program for
  Tug of War 
*/
class TugOfWar
{
	constructor()
	{
		this.difference = Number.MAX_VALUE;
	}
	//Display elements of given array
	printArray(arr, size)
	{
		for (var i = 0; i < size; ++i)
		{
			process.stdout.write("  " + arr[i]);
		}
		process.stdout.write("\n");
	}
	// Returns the difference of two numbers
	getDifference(a, b)
	{
		if (a > b)
		{
			return a - b;
		}
		else
		{
			return b - a;
		}
	}
	// Find two subsets of minimum difference
	subset(arr, visit, result, n, sum, i, j, k)
	{
		// When result are found or no need to visit current element
		if (j == parseInt(n / 2) || i == n || visit[i] == true || this.difference == 0)
		{
			return;
		}
		// Visit to next element through by recursion
		this.subset(arr, visit, result, n, sum, i + 1, j, k);
		// Set current element are active (used)
		visit[i] = true;
		if (j == (parseInt(n / 2)) - 1)
		{
			if (this.getDifference(parseInt(sum / 2), k + arr[i]) < this.difference)
			{
				// When a new minimum difference is obtained
				this.difference = this.getDifference(parseInt(sum / 2), k + arr[i]);
				// Get the new result
				for (var l = 0; l < n; ++l)
				{
					result[l] = visit[l];
				}
			}
		}
		// Visit to next element through by recursion
		this.subset(arr, visit, result, n, sum, i + 1, j + 1, k + arr[i]);
		// Change status of visited element
		visit[i] = false;
	}
	// Handles the request to find subset of minimum sum
	tugOfWar(arr, n)
	{
		if (n <= 1)
		{
			return;
		}
		// Loop controlling variable
		var i = 0;
		// This are used to find subset result
		var visit = Array(n).fill(false);
		var result = Array(n).fill(false);
		// Initialize current sum
		var sum = 0;
		for (i = 0; i < n; ++i)
		{
			sum = sum + arr[i];
		}
		this.printArray(arr, n);
		// Display the calculated total sum
		process.stdout.write("  Total Sum : " + sum + " \n");
		this.difference = Number.MAX_VALUE;
		// Find subset
		this.subset(arr, visit, result, n, sum, 0, 0, 0);
		// Reset the sum value
		// Reset the sum value
		sum = 0;
		// Display elements of first set A
		for (i = 0; i < n; ++i)
		{
			if (result[i] == false)
			{
				process.stdout.write("  " + arr[i]);
				sum = sum + arr[i];
			}
		}
		// Display the sum of set A
		process.stdout.write("\n  Set A Sum : " + sum + " \n");
		// Reset the sum value
		sum = 0;
		// Display elements of first set B
		for (i = 0; i < n; ++i)
		{
			if (result[i] == true)
			{
				process.stdout.write("  " + arr[i]);
				sum = sum + arr[i];
			}
		}
		// Display the sum of set B
		process.stdout.write("\n  Set B Sum : " + sum + "\n");
	}
}

function main()
{
	var task = new TugOfWar();
	// Define array of integer elements
	var arr = [6, 8, 35, -24, 62, 82, 13, 56, 32];
	// Get the size
	var n = arr.length;
	task.tugOfWar(arr, n);
}
main();

Output

  6  8  35  -24  62  82  13  56  32
  Total Sum : 270
  6  35  -24  62  56
  Set A Sum : 135
  8  82  13  32
  Set B Sum : 135
import sys
#   Python 3 Program for
#   Tug of War 

class TugOfWar :
	
	def __init__(self) :
		self.difference = sys.maxsize
	
	# Display elements of given array
	def printArray(self, arr, size) :
		i = 0
		while (i < size) :
			print("  ", arr[i], end = "")
			i += 1
		
		print(end = "\n")
	
	#  Returns the difference of two numbers
	def getDifference(self, a, b) :
		if (a > b) :
			return a - b
		else :
			return b - a
		
	
	#  Find two subsets of minimum difference
	def subset(self, arr, visit, result, n, sum, i, j, k) :
		#  When result are found or no need to visit current element
		if (j == int(n / 2) or i == n or visit[i] == True or self.difference == 0) :
			return
		
		#  Visit to next element through by recursion
		self.subset(arr, visit, result, n, sum, i + 1, j, k)
		#  Set current element are active (used)
		visit[i] = True
		if (j == (int(n / 2)) - 1) :
			if (self.getDifference(int(sum / 2), k + arr[i]) < self.difference) :
				#  When a new minimum difference is obtained
				self.difference = self.getDifference(int(sum / 2), k + arr[i])
				#  Get the new result
				l = 0
				while (l < n) :
					result[l] = visit[l]
					l += 1
				
			
		
		#  Visit to next element through by recursion
		self.subset(arr, visit, result, n, sum, i + 1, j + 1, k + arr[i])
		#  Change status of visited element
		visit[i] = False
	
	#  Handles the request to find subset of minimum sum
	def tugOfWar(self, arr, n) :
		if (n <= 1) :
			return
		
		#  Loop controlling variable
		i = 0
		#  This are used to find subset result
		visit = [False] * (n)
		result = [False] * (n)
		#  Initialize current sum
		sum = 0
		while (i < n) :
			sum = sum + arr[i]
			i += 1
		
		self.printArray(arr, n)
		#  Display the calculated total sum
		print("  Total Sum : ", sum ," ")
		self.difference = sys.maxsize
		#  Find subset
		self.subset(arr, visit, result, n, sum, 0, 0, 0)
		#  Reset the sum value
		#  Reset the sum value
		sum = 0
		#  Display elements of first set A
		i = 0
		while (i < n) :
			if (result[i] == False) :
				print("  ", arr[i], end = "")
				sum = sum + arr[i]
			
			i += 1
		
		#  Display the sum of set A
		print("\n  Set A Sum : ", sum ," ")
		#  Reset the sum value
		sum = 0
		#  Display elements of first set B
		i = 0
		while (i < n) :
			if (result[i] == True) :
				print("  ", arr[i], end = "")
				sum = sum + arr[i]
			
			i += 1
		
		#  Display the sum of set B
		print("\n  Set B Sum : ", sum )
	

def main() :
	task = TugOfWar()
	#  Define array of integer elements
	arr = [6, 8, 35, -24, 62, 82, 13, 56, 32]
	#  Get the size
	n = len(arr)
	task.tugOfWar(arr, n)

if __name__ == "__main__": main()

Output

   6   8   35   -24   62   82   13   56   32
  Total Sum :  270
   6   35   -24   62   56
  Set A Sum :  135
   8   82   13   32
  Set B Sum :  135
#   Ruby Program for
#   Tug of War 

class TugOfWar  
	# Define the accessor and reader of class TugOfWar  
	attr_reader :difference
	attr_accessor :difference
 
	
	def initialize() 
		self.difference = (2 ** (0. size * 8 - 2))
	end

	# Display elements of given array
	def printArray(arr, size) 
		i = 0
		while (i < size) 
			print("  ", arr[i])
			i += 1
		end

		print("\n")
	end

	#  Returns the difference of two numbers
	def getDifference(a, b) 
		if (a > b) 
			return a - b
		else 
			return b - a
		end

	end

	#  Find two subsets of minimum difference
	def subset(arr, visit, result, n, sum, i, j, k) 
		#  When result are found or no need to visit current element
		if (j == n / 2 || i == n || visit[i] == true || self.difference == 0) 
			return
		end

		#  Visit to next element through by recursion
		self.subset(arr, visit, result, n, sum, i + 1, j, k)
		#  Set current element are active (used)
		visit[i] = true
		if (j == (n / 2) - 1) 
			if (self.getDifference(sum / 2, k + arr[i]) < self.difference) 
				#  When a new minimum difference is obtained
				self.difference = self.getDifference(sum / 2, k + arr[i])
				#  Get the new result
				l = 0
				while (l < n) 
					result[l] = visit[l]
					l += 1
				end

			end

		end

		#  Visit to next element through by recursion
		self.subset(arr, visit, result, n, sum, i + 1, j + 1, k + arr[i])
		#  Change status of visited element
		visit[i] = false
	end

	#  Handles the request to find subset of minimum sum
	def tugOfWar(arr, n) 
		if (n <= 1) 
			return
		end

		#  Loop controlling variable
		i = 0
		#  This are used to find subset result
		visit = Array.new(n) {false}
		result = Array.new(n) {false}
		#  Initialize current sum
		sum = 0
		while (i < n) 
			sum = sum + arr[i]
			i += 1
		end

		self.printArray(arr, n)
		#  Display the calculated total sum
		print("  Total Sum : ", sum ," \n")
		self.difference = (2 ** (0. size * 8 - 2))
		#  Find subset
		self.subset(arr, visit, result, n, sum, 0, 0, 0)
		#  Reset the sum value
		#  Reset the sum value
		sum = 0
		#  Display elements of first set A
		i = 0
		while (i < n) 
			if (result[i] == false) 
				print("  ", arr[i])
				sum = sum + arr[i]
			end

			i += 1
		end

		#  Display the sum of set A
		print("\n  Set A Sum : ", sum ," \n")
		#  Reset the sum value
		sum = 0
		#  Display elements of first set B
		i = 0
		while (i < n) 
			if (result[i] == true) 
				print("  ", arr[i])
				sum = sum + arr[i]
			end

			i += 1
		end

		#  Display the sum of set B
		print("\n  Set B Sum : ", sum ,"\n")
	end

end

def main() 
	task = TugOfWar.new()
	#  Define array of integer elements
	arr = [6, 8, 35, -24, 62, 82, 13, 56, 32]
	#  Get the size
	n = arr.length
	task.tugOfWar(arr, n)
end

main()

Output

  6  8  35  -24  62  82  13  56  32
  Total Sum : 270 
  6  35  -24  62  56
  Set A Sum : 135 
  8  82  13  32
  Set B Sum : 135

/*
  Scala Program for
  Tug of War 
*/
class TugOfWar(var difference: Int)
{
	def this()
	{
		this(Int.MaxValue);
	}
	//Display elements of given array
	def printArray(arr: Array[Int], size: Int): Unit = {
		var i: Int = 0;
		while (i < size)
		{
			print("  " + arr(i));
			i += 1;
		}
		print("\n");
	}
	// Returns the difference of two numbers
	def getDifference(a: Int, b: Int): Int = {
		if (a > b)
		{
			return a - b;
		}
		else
		{
			return b - a;
		}
	}
	// Find two subsets of minimum difference
	def subset(arr: Array[Int], visit: Array[Boolean], result: Array[Boolean], n: Int, sum: Int, i: Int, j: Int, k: Int): Unit = {
		// When result are found or no need to visit current element
		if (j == (n / 2).toInt || i == n || visit(i) == true || this.difference == 0)
		{
			return;
		}
		// Visit to next element through by recursion
		this.subset(arr, visit, result, n, sum, i + 1, j, k);
		// Set current element are active (used)
		visit(i) = true;
		if (j == ((n / 2).toInt) - 1)
		{
			if (this.getDifference((sum / 2).toInt, k + arr(i)) < this.difference)
			{
				// When a new minimum difference is obtained
				this.difference = this.getDifference((sum / 2).toInt, k + arr(i));
				// Get the new result
				var l: Int = 0;
				while (l < n)
				{
					result(l) = visit(l);
					l += 1;
				}
			}
		}
		// Visit to next element through by recursion
		this.subset(arr, visit, result, n, sum, i + 1, j + 1, k + arr(i));
		// Change status of visited element
		visit(i) = false;
	}
	// Handles the request to find subset of minimum sum
	def tugOfWar(arr: Array[Int], n: Int): Unit = {
		if (n <= 1)
		{
			return;
		}
		// Loop controlling variable
		var i: Int = 0;
		// This are used to find subset result
		var visit: Array[Boolean] = Array.fill[Boolean](n)(false);
		var result: Array[Boolean] = Array.fill[Boolean](n)(false);
		// Initialize current sum
		var sum: Int = 0;
		while (i < n)
		{
			sum = sum + arr(i);
			i += 1;
		}
		this.printArray(arr, n);
		// Display the calculated total sum
		print("  Total Sum : " + sum + " \n");
		this.difference = Int.MaxValue;
		// Find subset
		this.subset(arr, visit, result, n, sum, 0, 0, 0);
		// Reset the sum value
		// Reset the sum value
		sum = 0;
		// Display elements of first set A
		i = 0;
		while (i < n)
		{
			if (result(i) == false)
			{
				print("  " + arr(i));
				sum = sum + arr(i);
			}
			i += 1;
		}
		// Display the sum of set A
		print("\n  Set A Sum : " + sum + " \n");
		// Reset the sum value
		sum = 0;
		// Display elements of first set B
		i = 0;
		while (i < n)
		{
			if (result(i) == true)
			{
				print("  " + arr(i));
				sum = sum + arr(i);
			}
			i += 1;
		}
		// Display the sum of set B
		print("\n  Set B Sum : " + sum + "\n");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: TugOfWar = new TugOfWar();
		// Define array of integer elements
		var arr: Array[Int] = Array(6, 8, 35, -24, 62, 82, 13, 56, 32);
		// Get the size
		var n: Int = arr.length;
		task.tugOfWar(arr, n);
	}
}

Output

  6  8  35  -24  62  82  13  56  32
  Total Sum : 270
  6  35  -24  62  56
  Set A Sum : 135
  8  82  13  32
  Set B Sum : 135
/*
  Swift 4 Program for
  Tug of War 
*/
class TugOfWar
{
	var difference: Int;
	init()
	{
		self.difference = Int.max;
	}
	//Display elements of given array
	func printArray(_ arr: [Int], _ size: Int)
	{
		var i: Int = 0;
		while (i < size)
		{
			print("  ", arr[i], terminator: "");
			i += 1;
		}
		print(terminator: "\n");
	}
	// Returns the difference of two numbers
	func getDifference(_ a: Int, _ b: Int)->Int
	{
		if (a > b)
		{
			return a - b;
		}
		else
		{
			return b - a;
		}
	}
	// Find two subsets of minimum difference
	func subset(_ arr: [Int], _ visit: inout[Bool], _ result: inout[Bool], _ n: Int, _ sum: Int, _ i: Int, _ j: Int, _ k: Int)
	{
		// When result are found or no need to visit current element
		if (j == n / 2 || i == n || visit[i] == true || self.difference == 0)
		{
			return;
		}
		// Visit to next element through by recursion
		self.subset(arr, &visit, &result, n, sum, i + 1, j, k);
		// Set current element are active (used)
		visit[i] = true;
		if (j == (n / 2) - 1)
		{
			if (self.getDifference(sum / 2, k + arr[i]) < self.difference)
			{
				// When a new minimum difference is obtained
				self.difference = self.getDifference(sum / 2, k + arr[i]);
				// Get the new result
				var l: Int = 0;
				while (l < n)
				{
					result[l] = visit[l];
					l += 1;
				}
			}
		}
		// Visit to next element through by recursion
		self.subset(arr, &visit, &result, n, sum, i + 1, j + 1, k + arr[i]);
		// Change status of visited element
		visit[i] = false;
	}
	// Handles the request to find subset of minimum sum
	func tugOfWar(_ arr: [Int], _ n: Int)
	{
		if (n <= 1)
		{
			return;
		}
		// Loop controlling variable
		var i: Int = 0;
		// This are used to find subset result
		var visit: [Bool] = Array(repeating: false, count: n);
		var result: [Bool] = Array(repeating: false, count: n);
		// Initialize current sum
		var sum: Int = 0;
		while (i < n)
		{
			sum = sum + arr[i];
			i += 1;
		}
		self.printArray(arr, n);
		// Display the calculated total sum
		print("  Total Sum : ", sum ," ");
		self.difference = Int.max;
		// Find subset
		self.subset(arr, &visit, &result, n, sum, 0, 0, 0);
		// Reset the sum value
		// Reset the sum value
		sum = 0;
		// Display elements of first set A
		i = 0;
		while (i < n)
		{
			if (result[i] == false)
			{
				print("  ", arr[i], terminator: "");
				sum = sum + arr[i];
			}
			i += 1;
		}
		// Display the sum of set A
		print("\n  Set A Sum : ", sum ," ");
		// Reset the sum value
		sum = 0;
		// Display elements of first set B
		i = 0;
		while (i < n)
		{
			if (result[i] == true)
			{
				print("  ", arr[i], terminator: "");
				sum = sum + arr[i];
			}
			i += 1;
		}
		// Display the sum of set B
		print("\n  Set B Sum : ", sum );
	}
}
func main()
{
	let task: TugOfWar = TugOfWar();
	// Define array of integer elements
	let arr: [Int] = [6, 8, 35, -24, 62, 82, 13, 56, 32];
	// Get the size
	let n: Int = arr.count;
	task.tugOfWar(arr, n);
}
main();

Output

   6   8   35   -24   62   82   13   56   32
  Total Sum :  270
   6   35   -24   62   56
  Set A Sum :  135
   8   82   13   32
  Set B Sum :  135
/*
  Kotlin Program for
  Tug of War 
*/
class TugOfWar
{
	var difference: Int;
	constructor()
	{
		this.difference = Int.MAX_VALUE;
	}
	//Display elements of given array
	fun printArray(arr: Array<Int> , size: Int): Unit
	{
		var i: Int = 0;
		while (i < size)
		{
			print("  " + arr[i]);
			i += 1;
		}
		print("\n");
	}
	// Returns the difference of two numbers
	fun getDifference(a: Int, b: Int): Int
	{
		if (a > b)
		{
			return a - b;
		}
		else
		{
			return b - a;
		}
	}
	// Find two subsets of minimum difference
	fun subset(arr: Array<Int> , visit: Array <Boolean> , result: Array <Boolean> , n: Int, sum: Int, i: Int, j: Int, k: Int): Unit
	{
		// When result are found or no need to visit current element
		if (j == n / 2 || i == n || visit[i] == true || this.difference == 0)
		{
			return;
		}
		// Visit to next element through by recursion
		this.subset(arr, visit, result, n, sum, i + 1, j, k);
		// Set current element are active (used)
		visit[i] = true;
		if (j == (n / 2) - 1)
		{
			if (this.getDifference(sum / 2, k + arr[i]) < this.difference)
			{
				// When a new minimum difference is obtained
				this.difference = this.getDifference(sum / 2, k + arr[i]);
				// Get the new result
				var l: Int = 0;
				while (l < n)
				{
					result[l] = visit[l];
					l += 1;
				}
			}
		}
		// Visit to next element through by recursion
		this.subset(arr, visit, result, n, sum, i + 1, j + 1, k + arr[i]);
		// Change status of visited element
		visit[i] = false;
	}
	// Handles the request to find subset of minimum sum
	fun tugOfWar(arr: Array <Int> , n: Int): Unit
	{
		if (n <= 1)
		{
			return;
		}
		// Loop controlling variable
		var i: Int = 0;
		// This are used to find subset result
		var visit: Array<Boolean> = Array(n)
		{
			false
		};
		var result: Array<Boolean> = Array(n)
		{
			false
		};
		// Initialize current sum
		var sum: Int = 0;
		while (i < n)
		{
			sum = sum + arr[i];
			i += 1;
		}
		this.printArray(arr, n);
		// Display the calculated total sum
		print("  Total Sum : " + sum + " \n");
		this.difference = Int.MAX_VALUE;
		// Find subset
		this.subset(arr, visit, result, n, sum, 0, 0, 0);
		// Reset the sum value
		// Reset the sum value
		sum = 0;
		// Display elements of first set A
		i = 0;
		while (i < n)
		{
			if (result[i] == false)
			{
				print("  " + arr[i]);
				sum = sum + arr[i];
			}
			i += 1;
		}
		// Display the sum of set A
		print("\n  Set A Sum : " + sum + " \n");
		// Reset the sum value
		sum = 0;
		// Display elements of first set B
		i = 0;
		while (i < n)
		{
			if (result[i] == true)
			{
				print("  " + arr[i]);
				sum = sum + arr[i];
			}
			i += 1;
		}
		// Display the sum of set B
		print("\n  Set B Sum : " + sum + "\n");
	}
}
fun main(args: Array <String> ): Unit
{
	var task: TugOfWar = TugOfWar();
	// Define array of integer elements
	var arr: Array < Int > = arrayOf(6, 8, 35, -24, 62, 82, 13, 56, 32);
	// Get the size
	var n: Int = arr.count();
	task.tugOfWar(arr, n);
}

Output

  6  8  35  -24  62  82  13  56  32
  Total Sum : 270
  6  35  -24  62  56
  Set A Sum : 135
  8  82  13  32
  Set B Sum : 135

Result Explanation

The given array is printed: [6, 8, 35, -24, 62, 82, 13, 56, 32]. The total sum of the array is calculated and displayed as 270.

The subsets A and B are then printed. The elements of A are [6, 35, -24, 62, 56] with a sum of 135. The elements of B are [8, 82, 13, 32] with a sum of 135 as well.

The algorithm calculates the subsets in such a way that the difference between the sums is minimized. In this case, both subsets have the same sum, resulting in a difference of 0.

Time Complexity

The time complexity of the Tug of War algorithm is O(2^n), where n is the size of the input array. The algorithm uses recursion and backtracking to explore all possible subsets. As a result, the number of recursive calls grows exponentially with the size of the input array.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment





Categories
Relative Post