Tug of War
Here given code implementation process.
// 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
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