K partition with equal sum
Given the collection of positive integers. Our goal is to partition of that elements into K parts with equal sum. Let an example.
collection[] = {6 , 2 , 7 , 1 , 8 , 4 , 5 , 3 , 9 , 15};
k = 2
Total Sum : 60
Partition size : 2
Equal sum is : 30
Output
------------------
Set 1 : 6 2 7 1 5 9
Set 2 : 8 4 3 15
k = 4
Total Sum : 60
Partition size : 4
Equal sum is : 15
Output
------------------
Set 1 : 6 2 7
Set 2 : 1 5 9
Set 3 : 8 4 3
Set 4 : 15
k = 3
Total Sum : 60
Partition size : 3
Equal sum is : 20
Output
------------------
Set 1 : 6 2 7 1 4
Set 2 : 8 3 9
Set 3 : 5 15
Here given code implementation process.
// C Program
// K partition with equal sum
#include <stdio.h>
// Find subset of given sum
int findSolution(int collection[], int result[], int visit[], int n, int k, int sum, int i, int j)
{
if (i >= n || j >= k)
{
return 0;
}
if (sum == result[j])
{
if (j + 1 == k)
{
// When all subsets exist
return 1;
}
else
{
// Backtrack next subset sum
return findSolution(collection, result, visit, n, k, sum, 0, j + 1);
}
}
// Execute loop through by size n
for (int x = i; x < n; ++x)
{
if (visit[x] == 0 && result[j] + collection[x] <= sum)
{
// Active visit status
visit[x] = j + 1;
result[j] = result[j] + collection[x];
if (findSolution(collection, result, visit, n, k, sum, i + 1, j) == 1)
{
// When solution is found
return 1;
}
// Back to previous values
result[j] = result[j] - collection[x];
visit[x] = 0;
}
}
return 0;
}
// Handles the request of partition of k with equal sum
void partition(int collection[], int n, int k)
{
if (k <= 0 || k > n)
{
printf("\n Given %d partition not possible\n", k);
}
else
{
int i = 0;
int j = 0;
int sum = 0;
// Sum of elements
for (i = 0; i < n; ++i)
{
sum += collection[i];
}
if (sum % k == 0)
{
// When partition possible of equal sum
// This is used to handle partition sum info
int result[k];
// This are used to track visited element
int visit[n];
// Through the loop set initial values
for (i = 0; i < n; ++i)
{
if (i < k)
{
result[i] = 0;
}
visit[i] = 0;
}
if (findSolution(collection, result, visit, n, k, sum / k, 0, 0))
{
// Display calculated result
printf("\n Total Sum : %d", sum);
printf("\n Partition size : %d", k);
printf("\n Equal sum is : %d", sum / k);
printf("\n Output");
printf("\n ------------------");
// Display resultant set
for (j = 1; j <= k; ++j)
{
printf("\n Set %d : ", j);
for (i = 0; i < n; ++i)
{
if (visit[i] == j)
{
printf(" %d", collection[i]);
}
}
}
printf("\n\n");
}
else
{
printf("\n Partition of size %d cannot be divided into equal amount\n", k);
}
}
else
{
printf("\n Partition with %d parts is not produce equal sum\n", k);
}
}
}
int main(int argc, char
const *argv[])
{
// Define collection of positive elements
int collection[] = {
6 , 2 , 7 , 1 , 8 , 4 , 5 , 3 , 9 , 15
};
// Get the number of elements
int n = sizeof(collection) / sizeof(collection[0]);
// Test cases
int k = 2;
partition(collection, n, k);
k = 4;
partition(collection, n, k);
k = 3;
partition(collection, n, k);
return 0;
}Output
Total Sum : 60
Partition size : 2
Equal sum is : 30
Output
------------------
Set 1 : 6 2 7 1 5 9
Set 2 : 8 4 3 15
Total Sum : 60
Partition size : 4
Equal sum is : 15
Output
------------------
Set 1 : 6 2 7
Set 2 : 1 5 9
Set 3 : 8 4 3
Set 4 : 15
Total Sum : 60
Partition size : 3
Equal sum is : 20
Output
------------------
Set 1 : 6 2 7 1 4
Set 2 : 8 3 9
Set 3 : 5 15
/*
Java Program for
K partition with equal sum
*/
class Subset
{
// Find subset of given sum
public boolean findSolution(int[] collection, int[] result, int[] visit, int n, int k, int sum, int i, int j)
{
if (i >= n || j >= k)
{
return false;
}
if (sum == result[j])
{
if (j + 1 == k)
{
// When all subsets exist
return true;
}
else
{
// Backtrack next subset sum
return findSolution(collection, result, visit, n, k, sum, 0, j + 1);
}
}
// Execute loop through by size n
for (int x = i; x < n; ++x)
{
if (visit[x] == 0 && result[j] + collection[x] <= sum)
{
// Active visit status
visit[x] = j + 1;
result[j] = result[j] + collection[x];
if (findSolution(collection, result, visit, n, k, sum, i + 1, j) == true)
{
// When solution is found
return true;
}
// Back to previous values
result[j] = result[j] - collection[x];
visit[x] = 0;
}
}
return false;
}
// Handles the request of partition of k with equal sum
public void partition(int[] collection, int n, int k)
{
if (k <= 0 || k > n)
{
System.out.print("\n Given " + k + " partition not possible\n");
}
else
{
// Loop controlling variable i and j
int i = 0;
int j = 0;
int sum = 0;
// Sum of elements
for (i = 0; i < n; ++i)
{
sum += collection[i];
}
if (sum % k == 0)
{
// When partition possible of equal sum
// This is used to handle partition sum info
int[] result = new int[k];
// This are used to track visited element
int[] visit = new int[n];
// Through the loop set initial values
for (i = 0; i < n; ++i)
{
if (i < k)
{
result[i] = 0;
}
visit[i] = 0;
}
if (findSolution(collection, result, visit, n, k, sum / k, 0, 0) == true)
{
// Display calculated result
System.out.print("\n Total Sum : " + sum + "");
System.out.print("\n Partition size : " + k + "");
System.out.print("\n Equal sum is : " + sum / k + "");
System.out.print("\n Output");
System.out.print("\n ------------------");
// Display resultant set
for (j = 1; j <= k; ++j)
{
System.out.print("\n Set " + j + " : ");
for (i = 0; i < n; ++i)
{
if (visit[i] == j)
{
System.out.print(" " + collection[i]);
}
}
}
System.out.print("\n\n");
}
else
{
System.out.print("\n Partition of size " + k + " cannot be divided into equal amount\n");
}
}
else
{
System.out.print("\n Partition with " + k + " parts is not produce equal sum\n");
}
}
}
public static void main(String[] args)
{
Subset task = new Subset();
// Define collection of positive elements
int[] collection = {
6 , 2 , 7 , 1 , 8 , 4 , 5 , 3 , 9 , 15
};
// Get the number of elements
int n = collection.length;
// Test cases
int k = 2;
task.partition(collection, n, k);
k = 4;
task.partition(collection, n, k);
k = 3;
task.partition(collection, n, k);
}
}Output
Total Sum : 60
Partition size : 2
Equal sum is : 30
Output
------------------
Set 1 : 6 2 7 1 5 9
Set 2 : 8 4 3 15
Total Sum : 60
Partition size : 4
Equal sum is : 15
Output
------------------
Set 1 : 6 2 7
Set 2 : 1 5 9
Set 3 : 8 4 3
Set 4 : 15
Total Sum : 60
Partition size : 3
Equal sum is : 20
Output
------------------
Set 1 : 6 2 7 1 4
Set 2 : 8 3 9
Set 3 : 5 15
// Include header file
#include <iostream>
using namespace std;
/*
C++ Program for
K partition with equal sum
*/
class Subset
{
public:
// Find subset of given sum
bool findSolution(int collection[], int result[], int visit[], int n, int k, int sum, int i, int j)
{
if (i >= n || j >= k)
{
return false;
}
if (sum == result[j])
{
if (j + 1 == k)
{
// When all subsets exist
return true;
}
else
{
// Backtrack next subset sum
return this->findSolution(collection, result, visit, n, k, sum, 0, j + 1);
}
}
// Execute loop through by size n
for (int x = i; x < n; ++x)
{
if (visit[x] == 0 && result[j] + collection[x] <= sum)
{
// Active visit status
visit[x] = j + 1;
result[j] = result[j] + collection[x];
if (this->findSolution(collection, result, visit, n, k, sum, i + 1, j) == true)
{
// When solution is found
return true;
}
// Back to previous values
result[j] = result[j] - collection[x];
visit[x] = 0;
}
}
return false;
}
// Handles the request of partition of k with equal sum
void partition(int collection[], int n, int k)
{
if (k <= 0 || k > n)
{
cout << "\n Given " << k << " partition not possible\n";
}
else
{
// Loop controlling variable i and j
int i = 0;
int j = 0;
int sum = 0;
// Sum of elements
for (i = 0; i < n; ++i)
{
sum += collection[i];
}
if (sum % k == 0)
{
// When partition possible of equal sum
// This is used to handle partition sum info
int result[k];
// This are used to track visited element
int visit[n];
// Through the loop set initial values
for (i = 0; i < n; ++i)
{
if (i < k)
{
result[i] = 0;
}
visit[i] = 0;
}
if (this->findSolution(collection, result, visit, n, k, sum / k, 0, 0) == true)
{
// Display calculated result
cout << "\n Total Sum : " << sum << "";
cout << "\n Partition size : " << k << "";
cout << "\n Equal sum is : " << sum / k << "";
cout << "\n Output";
cout << "\n ------------------";
// Display resultant set
for (j = 1; j <= k; ++j)
{
cout << "\n Set " << j << " : ";
for (i = 0; i < n; ++i)
{
if (visit[i] == j)
{
cout << " " << collection[i];
}
}
}
cout << "\n\n";
}
else
{
cout << "\n Partition of size " << k << " cannot be divided into equal amount\n";
}
}
else
{
cout << "\n Partition with " << k << " parts is not produce equal sum\n";
}
}
}
};
int main()
{
Subset task = Subset();
// Define collection of positive elements
int collection[] = {
6 , 2 , 7 , 1 , 8 , 4 , 5 , 3 , 9 , 15
};
// Get the number of elements
int n = sizeof(collection) / sizeof(collection[0]);
// Test cases
int k = 2;
task.partition(collection, n, k);
k = 4;
task.partition(collection, n, k);
k = 3;
task.partition(collection, n, k);
return 0;
}Output
Total Sum : 60
Partition size : 2
Equal sum is : 30
Output
------------------
Set 1 : 6 2 7 1 5 9
Set 2 : 8 4 3 15
Total Sum : 60
Partition size : 4
Equal sum is : 15
Output
------------------
Set 1 : 6 2 7
Set 2 : 1 5 9
Set 3 : 8 4 3
Set 4 : 15
Total Sum : 60
Partition size : 3
Equal sum is : 20
Output
------------------
Set 1 : 6 2 7 1 4
Set 2 : 8 3 9
Set 3 : 5 15
// Include namespace system
using System;
/*
C# Program for
K partition with equal sum
*/
public class Subset
{
// Find subset of given sum
public Boolean findSolution(int[] collection, int[] result, int[] visit, int n, int k, int sum, int i, int j)
{
if (i >= n || j >= k)
{
return false;
}
if (sum == result[j])
{
if (j + 1 == k)
{
// When all subsets exist
return true;
}
else
{
// Backtrack next subset sum
return findSolution(collection, result, visit, n, k, sum, 0, j + 1);
}
}
// Execute loop through by size n
for (int x = i; x < n; ++x)
{
if (visit[x] == 0 && result[j] + collection[x] <= sum)
{
// Active visit status
visit[x] = j + 1;
result[j] = result[j] + collection[x];
if (findSolution(collection, result, visit, n, k, sum, i + 1, j) == true)
{
// When solution is found
return true;
}
// Back to previous values
result[j] = result[j] - collection[x];
visit[x] = 0;
}
}
return false;
}
// Handles the request of partition of k with equal sum
public void partition(int[] collection, int n, int k)
{
if (k <= 0 || k > n)
{
Console.Write("\n Given " + k + " partition not possible\n");
}
else
{
// Loop controlling variable i and j
int i = 0;
int j = 0;
int sum = 0;
// Sum of elements
for (i = 0; i < n; ++i)
{
sum += collection[i];
}
if (sum % k == 0)
{
// When partition possible of equal sum
// This is used to handle partition sum info
int[] result = new int[k];
// This are used to track visited element
int[] visit = new int[n];
// Through the loop set initial values
for (i = 0; i < n; ++i)
{
if (i < k)
{
result[i] = 0;
}
visit[i] = 0;
}
if (findSolution(collection, result, visit, n, k, sum / k, 0, 0) == true)
{
// Display calculated result
Console.Write("\n Total Sum : " + sum + "");
Console.Write("\n Partition size : " + k + "");
Console.Write("\n Equal sum is : " + sum / k + "");
Console.Write("\n Output");
Console.Write("\n ------------------");
// Display resultant set
for (j = 1; j <= k; ++j)
{
Console.Write("\n Set " + j + " : ");
for (i = 0; i < n; ++i)
{
if (visit[i] == j)
{
Console.Write(" " + collection[i]);
}
}
}
Console.Write("\n\n");
}
else
{
Console.Write("\n Partition of size " + k + " cannot be divided into equal amount\n");
}
}
else
{
Console.Write("\n Partition with " + k + " parts is not produce equal sum\n");
}
}
}
public static void Main(String[] args)
{
Subset task = new Subset();
// Define collection of positive elements
int[] collection = {
6 , 2 , 7 , 1 , 8 , 4 , 5 , 3 , 9 , 15
};
// Get the number of elements
int n = collection.Length;
// Test cases
int k = 2;
task.partition(collection, n, k);
k = 4;
task.partition(collection, n, k);
k = 3;
task.partition(collection, n, k);
}
}Output
Total Sum : 60
Partition size : 2
Equal sum is : 30
Output
------------------
Set 1 : 6 2 7 1 5 9
Set 2 : 8 4 3 15
Total Sum : 60
Partition size : 4
Equal sum is : 15
Output
------------------
Set 1 : 6 2 7
Set 2 : 1 5 9
Set 3 : 8 4 3
Set 4 : 15
Total Sum : 60
Partition size : 3
Equal sum is : 20
Output
------------------
Set 1 : 6 2 7 1 4
Set 2 : 8 3 9
Set 3 : 5 15
<?php
/*
Php Program for
K partition with equal sum
*/
class Subset
{
// Find subset of given sum
public function findSolution( & $collection, & $result, & $visit, $n, $k, $sum, $i, $j)
{
if ($i >= $n || $j >= $k)
{
return false;
}
if ($sum == $result[$j])
{
if ($j + 1 == $k)
{
// When all subsets exist
return true;
}
else
{
// Backtrack next subset sum
return $this->findSolution($collection, $result, $visit, $n, $k, $sum, 0, $j + 1);
}
}
// Execute loop through by size n
for ($x = $i; $x < $n; ++$x)
{
if ($visit[$x] == 0 && $result[$j] + $collection[$x] <= $sum)
{
// Active visit status
$visit[$x] = $j + 1;
$result[$j] = $result[$j] + $collection[$x];
if ($this->findSolution($collection, $result, $visit, $n, $k, $sum, $i + 1, $j) == true)
{
// When solution is found
return true;
}
// Back to previous values
$result[$j] = $result[$j] - $collection[$x];
$visit[$x] = 0;
}
}
return false;
}
// Handles the request of partition of k with equal sum
public function partition( & $collection, $n, $k)
{
if ($k <= 0 || $k > $n)
{
echo "\n Given ". $k ." partition not possible\n";
}
else
{
// Loop controlling variable i and j
$i = 0;
$j = 0;
$sum = 0;
// Sum of elements
for ($i = 0; $i < $n; ++$i)
{
$sum += $collection[$i];
}
if ($sum % $k == 0)
{
// When partition possible of equal sum
// This is used to handle partition sum info
$result = array_fill(0, $k, 0);
// This are used to track visited element
$visit = array_fill(0, $n, 0);
if ($this->findSolution($collection, $result, $visit, $n, $k, intval($sum / $k), 0, 0) == true)
{
// Display calculated result
echo "\n Total Sum : ". $sum ."";
echo "\n Partition size : ". $k ."";
echo "\n Equal sum is : ". intval($sum / $k) ."";
echo "\n Output";
echo "\n ------------------";
// Display resultant set
for ($j = 1; $j <= $k; ++$j)
{
echo "\n Set ". $j ." : ";
for ($i = 0; $i < $n; ++$i)
{
if ($visit[$i] == $j)
{
echo " ". $collection[$i];
}
}
}
echo "\n\n";
}
else
{
echo "\n Partition of size ". $k ." cannot be divided into equal amount\n";
}
}
else
{
echo "\n Partition with ". $k ." parts is not produce equal sum\n";
}
}
}
}
function main()
{
$task = new Subset();
// Define collection of positive elements
$collection = array(6, 2, 7, 1, 8, 4, 5, 3, 9, 15);
// Get the number of elements
$n = count($collection);
// Test cases
$k = 2;
$task->partition($collection, $n, $k);
$k = 4;
$task->partition($collection, $n, $k);
$k = 3;
$task->partition($collection, $n, $k);
}
main();Output
Total Sum : 60
Partition size : 2
Equal sum is : 30
Output
------------------
Set 1 : 6 2 7 1 5 9
Set 2 : 8 4 3 15
Total Sum : 60
Partition size : 4
Equal sum is : 15
Output
------------------
Set 1 : 6 2 7
Set 2 : 1 5 9
Set 3 : 8 4 3
Set 4 : 15
Total Sum : 60
Partition size : 3
Equal sum is : 20
Output
------------------
Set 1 : 6 2 7 1 4
Set 2 : 8 3 9
Set 3 : 5 15
/*
Node Js Program for
K partition with equal sum
*/
class Subset
{
// Find subset of given sum
findSolution(collection, result, visit, n, k, sum, i, j)
{
if (i >= n || j >= k)
{
return false;
}
if (sum == result[j])
{
if (j + 1 == k)
{
// When all subsets exist
return true;
}
else
{
// Backtrack next subset sum
return this.findSolution(collection, result, visit, n, k, sum, 0, j + 1);
}
}
// Execute loop through by size n
for (var x = i; x < n; ++x)
{
if (visit[x] == 0 && result[j] + collection[x] <= sum)
{
// Active visit status
visit[x] = j + 1;
result[j] = result[j] + collection[x];
if (this.findSolution(collection, result, visit, n, k, sum, i + 1, j) == true)
{
// When solution is found
return true;
}
// Back to previous values
result[j] = result[j] - collection[x];
visit[x] = 0;
}
}
return false;
}
// Handles the request of partition of k with equal sum
partition(collection, n, k)
{
if (k <= 0 || k > n)
{
process.stdout.write("\n Given " + k + " partition not possible\n");
}
else
{
// Loop controlling variable i and j
var i = 0;
var j = 0;
var sum = 0;
// Sum of elements
for (i = 0; i < n; ++i)
{
sum += collection[i];
}
if (sum % k == 0)
{
// When partition possible of equal sum
// This is used to handle partition sum info
var result = Array(k).fill(0);
// This are used to track visited element
var visit = Array(n).fill(0);
if (this.findSolution(collection, result, visit, n, k, parseInt(sum / k), 0, 0) == true)
{
// Display calculated result
process.stdout.write("\n Total Sum : " + sum + "");
process.stdout.write("\n Partition size : " + k + "");
process.stdout.write("\n Equal sum is : " + parseInt(sum / k) + "");
process.stdout.write("\n Output");
process.stdout.write("\n ------------------");
// Display resultant set
for (j = 1; j <= k; ++j)
{
process.stdout.write("\n Set " + j + " : ");
for (i = 0; i < n; ++i)
{
if (visit[i] == j)
{
process.stdout.write(" " + collection[i]);
}
}
}
process.stdout.write("\n\n");
}
else
{
process.stdout.write("\n Partition of size " + k + " cannot be divided into equal amount\n");
}
}
else
{
process.stdout.write("\n Partition with " + k + " parts is not produce equal sum\n");
}
}
}
}
function main()
{
var task = new Subset();
// Define collection of positive elements
var collection = [6, 2, 7, 1, 8, 4, 5, 3, 9, 15];
// Get the number of elements
var n = collection.length;
// Test cases
var k = 2;
task.partition(collection, n, k);
k = 4;
task.partition(collection, n, k);
k = 3;
task.partition(collection, n, k);
}
main();Output
Total Sum : 60
Partition size : 2
Equal sum is : 30
Output
------------------
Set 1 : 6 2 7 1 5 9
Set 2 : 8 4 3 15
Total Sum : 60
Partition size : 4
Equal sum is : 15
Output
------------------
Set 1 : 6 2 7
Set 2 : 1 5 9
Set 3 : 8 4 3
Set 4 : 15
Total Sum : 60
Partition size : 3
Equal sum is : 20
Output
------------------
Set 1 : 6 2 7 1 4
Set 2 : 8 3 9
Set 3 : 5 15
# Python 3 Program for
# K partition with equal sum
class Subset :
# Find subset of given sum
def findSolution(self, collection, result, visit, n, k, sum, i, j) :
if (i >= n or j >= k) :
return False
if (sum == result[j]) :
if (j + 1 == k) :
# When all subsets exist
return True
else :
# Backtrack next subset sum
return self.findSolution(collection, result, visit, n, k, sum, 0, j + 1)
# Execute loop through by size n
x = i
while (x < n) :
if (visit[x] == 0 and result[j] + collection[x] <= sum) :
# Active visit status
visit[x] = j + 1
result[j] = result[j] + collection[x]
if (self.findSolution(collection, result, visit, n, k, sum, i + 1, j) == True) :
# When solution is found
return True
# Back to previous values
result[j] = result[j] - collection[x]
visit[x] = 0
x += 1
return False
# Handles the request of partition of k with equal sum
def partition(self, collection, n, k) :
if (k <= 0 or k > n) :
print("\n Given ", k ," partition not possible")
else :
# Loop controlling variable i and j
i = 0
j = 0
sum = 0
# Sum of elements
while (i < n) :
sum += collection[i]
i += 1
if (sum % k == 0) :
# When partition possible of equal sum
# This is used to handle partition sum info
result = [0] * (k)
# This are used to track visited element
visit = [0] * (n)
if (self.findSolution(collection, result, visit, n, k, int(sum / k), 0, 0) == True) :
# Display calculated result
print("\n Total Sum : ", sum ,"", end = "")
print("\n Partition size : ", k ,"", end = "")
print("\n Equal sum is : ", int(sum / k) ,"", end = "")
print("\n Output", end = "")
print("\n ------------------", end = "")
# Display resultant set
j = 1
while (j <= k) :
print("\n Set ", j ," : ", end = "")
i = 0
while (i < n) :
if (visit[i] == j) :
print(" ", collection[i], end = "")
i += 1
j += 1
print("\n")
else :
print("\n Partition of size ", k ," cannot be divided into equal amount")
else :
print("\n Partition with ", k ," parts is not produce equal sum")
def main() :
task = Subset()
# Define collection of positive elements
collection = [6, 2, 7, 1, 8, 4, 5, 3, 9, 15]
# Get the number of elements
n = len(collection)
# Test cases
k = 2
task.partition(collection, n, k)
k = 4
task.partition(collection, n, k)
k = 3
task.partition(collection, n, k)
if __name__ == "__main__": main()Output
Total Sum : 60
Partition size : 2
Equal sum is : 30
Output
------------------
Set 1 : 6 2 7 1 5 9
Set 2 : 8 4 3 15
Total Sum : 60
Partition size : 4
Equal sum is : 15
Output
------------------
Set 1 : 6 2 7
Set 2 : 1 5 9
Set 3 : 8 4 3
Set 4 : 15
Total Sum : 60
Partition size : 3
Equal sum is : 20
Output
------------------
Set 1 : 6 2 7 1 4
Set 2 : 8 3 9
Set 3 : 5 15
# Ruby Program for
# K partition with equal sum
class Subset
# Find subset of given sum
def findSolution(collection, result, visit, n, k, sum, i, j)
if (i >= n || j >= k)
return false
end
if (sum == result[j])
if (j + 1 == k)
# When all subsets exist
return true
else
# Backtrack next subset sum
return self.findSolution(collection, result, visit, n, k, sum, 0, j + 1)
end
end
# Execute loop through by size n
x = i
while (x < n)
if (visit[x] == 0 && result[j] + collection[x] <= sum)
# Active visit status
visit[x] = j + 1
result[j] = result[j] + collection[x]
if (self.findSolution(collection, result, visit, n, k, sum, i + 1, j) == true)
# When solution is found
return true
end
# Back to previous values
result[j] = result[j] - collection[x]
visit[x] = 0
end
x += 1
end
return false
end
# Handles the request of partition of k with equal sum
def partition(collection, n, k)
if (k <= 0 || k > n)
print("\n Given ", k ," partition not possible\n")
else
# Loop controlling variable i and j
i = 0
j = 0
sum = 0
# Sum of elements
while (i < n)
sum += collection[i]
i += 1
end
if (sum % k == 0)
# When partition possible of equal sum
# This is used to handle partition sum info
result = Array.new(k) {0}
# This are used to track visited element
visit = Array.new(n) {0}
if (self.findSolution(collection, result, visit, n, k, sum / k, 0, 0) == true)
# Display calculated result
print("\n Total Sum : ", sum ,"")
print("\n Partition size : ", k ,"")
print("\n Equal sum is : ", sum / k ,"")
print("\n Output")
print("\n ------------------")
# Display resultant set
j = 1
while (j <= k)
print("\n Set ", j ," : ")
i = 0
while (i < n)
if (visit[i] == j)
print(" ", collection[i])
end
i += 1
end
j += 1
end
print("\n\n")
else
print("\n Partition of size ", k ," cannot be divided into equal amount\n")
end
else
print("\n Partition with ", k ," parts is not produce equal sum\n")
end
end
end
end
def main()
task = Subset.new()
# Define collection of positive elements
collection = [6, 2, 7, 1, 8, 4, 5, 3, 9, 15]
# Get the number of elements
n = collection.length
# Test cases
k = 2
task.partition(collection, n, k)
k = 4
task.partition(collection, n, k)
k = 3
task.partition(collection, n, k)
end
main()Output
Total Sum : 60
Partition size : 2
Equal sum is : 30
Output
------------------
Set 1 : 6 2 7 1 5 9
Set 2 : 8 4 3 15
Total Sum : 60
Partition size : 4
Equal sum is : 15
Output
------------------
Set 1 : 6 2 7
Set 2 : 1 5 9
Set 3 : 8 4 3
Set 4 : 15
Total Sum : 60
Partition size : 3
Equal sum is : 20
Output
------------------
Set 1 : 6 2 7 1 4
Set 2 : 8 3 9
Set 3 : 5 15
/*
Scala Program for
K partition with equal sum
*/
class Subset
{
// Find subset of given sum
def findSolution(collection: Array[Int], result: Array[Int], visit: Array[Int], n: Int, k: Int, sum: Int, i: Int, j: Int): Boolean = {
if (i >= n || j >= k)
{
return false;
}
if (sum == result(j))
{
if (j + 1 == k)
{
// When all subsets exist
return true;
}
else
{
// Backtrack next subset sum
return this.findSolution(collection, result, visit, n, k, sum, 0, j + 1);
}
}
// Execute loop through by size n
var x: Int = i;
while (x < n)
{
if (visit(x) == 0 && result(j) + collection(x) <= sum)
{
// Active visit status
visit(x) = j + 1;
result(j) = result(j) + collection(x);
if (this.findSolution(collection, result, visit, n, k, sum, i + 1, j) == true)
{
// When solution is found
return true;
}
// Back to previous values
result(j) = result(j) - collection(x);
visit(x) = 0;
}
x += 1;
}
return false;
}
// Handles the request of partition of k with equal sum
def partition(collection: Array[Int], n: Int, k: Int): Unit = {
if (k <= 0 || k > n)
{
print("\n Given " + k + " partition not possible\n");
}
else
{
// Loop controlling variable i and j
var i: Int = 0;
var j: Int = 0;
var sum: Int = 0;
// Sum of elements
while (i < n)
{
sum += collection(i);
i += 1;
}
if (sum % k == 0)
{
// When partition possible of equal sum
// This is used to handle partition sum info
var result: Array[Int] = Array.fill[Int](k)(0);
// This are used to track visited element
var visit: Array[Int] = Array.fill[Int](n)(0);
if (this.findSolution(collection, result, visit, n, k, (sum / k).toInt, 0, 0) == true)
{
// Display calculated result
print("\n Total Sum : " + sum + "");
print("\n Partition size : " + k + "");
print("\n Equal sum is : " + (sum / k).toInt + "");
print("\n Output");
print("\n ------------------");
// Display resultant set
j = 1;
while (j <= k)
{
print("\n Set " + j + " : ");
i = 0;
while (i < n)
{
if (visit(i) == j)
{
print(" " + collection(i));
}
i += 1;
}
j += 1;
}
print("\n\n");
}
else
{
print("\n Partition of size " + k + " cannot be divided into equal amount\n");
}
}
else
{
print("\n Partition with " + k + " parts is not produce equal sum\n");
}
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Subset = new Subset();
// Define collection of positive elements
var collection: Array[Int] = Array(6, 2, 7, 1, 8, 4, 5, 3, 9, 15);
// Get the number of elements
var n: Int = collection.length;
// Test cases
var k: Int = 2;
task.partition(collection, n, k);
k = 4;
task.partition(collection, n, k);
k = 3;
task.partition(collection, n, k);
}
}Output
Total Sum : 60
Partition size : 2
Equal sum is : 30
Output
------------------
Set 1 : 6 2 7 1 5 9
Set 2 : 8 4 3 15
Total Sum : 60
Partition size : 4
Equal sum is : 15
Output
------------------
Set 1 : 6 2 7
Set 2 : 1 5 9
Set 3 : 8 4 3
Set 4 : 15
Total Sum : 60
Partition size : 3
Equal sum is : 20
Output
------------------
Set 1 : 6 2 7 1 4
Set 2 : 8 3 9
Set 3 : 5 15
/*
Swift 4 Program for
K partition with equal sum
*/
class Subset
{
// Find subset of given sum
func findSolution(_ collection: [Int], _ result: inout[Int], _ visit: inout[Int], _ n: Int, _ k: Int, _ sum: Int, _ i: Int, _ j: Int)->Bool
{
if (i >= n || j >= k)
{
return false;
}
if (sum == result[j])
{
if (j + 1 == k)
{
// When all subsets exist
return true;
}
else
{
// Backtrack next subset sum
return self.findSolution(collection, &result, &visit, n, k, sum, 0, j + 1);
}
}
// Execute loop through by size n
var x: Int = i;
while (x < n)
{
if (visit[x] == 0 && result[j] + collection[x] <= sum)
{
// Active visit status
visit[x] = j + 1;
result[j] = result[j] + collection[x];
if (self.findSolution(collection, &result, &visit, n, k, sum, i + 1, j) == true)
{
// When solution is found
return true;
}
// Back to previous values
result[j] = result[j] - collection[x];
visit[x] = 0;
}
x += 1;
}
return false;
}
// Handles the request of partition of k with equal sum
func partition(_ collection: [Int], _ n: Int, _ k: Int)
{
if (k <= 0 || k > n)
{
print("\n Given ", k ," partition not possible");
}
else
{
// Loop controlling variable i and j
var i: Int = 0;
var j: Int = 0;
var sum: Int = 0;
// Sum of elements
while (i < n)
{
sum += collection[i];
i += 1;
}
if (sum % k == 0)
{
// When partition possible of equal sum
// This is used to handle partition sum info
var result: [Int] = Array(repeating: 0, count: k);
// This are used to track visited element
var visit: [Int] = Array(repeating: 0, count: n);
if (self.findSolution(collection, &result, &visit, n, k, sum / k, 0, 0) == true)
{
// Display calculated result
print("\n Total Sum : ", sum ,"", terminator: "");
print("\n Partition size : ", k ,"", terminator: "");
print("\n Equal sum is : ", sum / k ,"", terminator: "");
print("\n Output", terminator: "");
print("\n ------------------", terminator: "");
// Display resultant set
j = 1;
while (j <= k)
{
print("\n Set ", j ," : ", terminator: "");
i = 0;
while (i < n)
{
if (visit[i] == j)
{
print(" ", collection[i], terminator: "");
}
i += 1;
}
j += 1;
}
print("\n");
}
else
{
print("\n Partition of size ", k ," cannot be divided into equal amount");
}
}
else
{
print("\n Partition with ", k ," parts is not produce equal sum");
}
}
}
}
func main()
{
let task: Subset = Subset();
// Define collection of positive elements
let collection: [Int] = [6, 2, 7, 1, 8, 4, 5, 3, 9, 15];
// Get the number of elements
let n: Int = collection.count;
// Test cases
var k: Int = 2;
task.partition(collection, n, k);
k = 4;
task.partition(collection, n, k);
k = 3;
task.partition(collection, n, k);
}
main();Output
Total Sum : 60
Partition size : 2
Equal sum is : 30
Output
------------------
Set 1 : 6 2 7 1 5 9
Set 2 : 8 4 3 15
Total Sum : 60
Partition size : 4
Equal sum is : 15
Output
------------------
Set 1 : 6 2 7
Set 2 : 1 5 9
Set 3 : 8 4 3
Set 4 : 15
Total Sum : 60
Partition size : 3
Equal sum is : 20
Output
------------------
Set 1 : 6 2 7 1 4
Set 2 : 8 3 9
Set 3 : 5 15
/*
Kotlin Program for
K partition with equal sum
*/
class Subset
{
// Find subset of given sum
fun findSolution(collection: Array <Int> , result: Array <Int> , visit: Array <Int> , n: Int, k: Int, sum: Int, i: Int, j: Int): Boolean
{
if (i >= n || j >= k)
{
return false;
}
if (sum == result[j])
{
if (j + 1 == k)
{
// When all subsets exist
return true;
}
else
{
// Backtrack next subset sum
return this.findSolution(collection, result, visit, n, k, sum, 0, j + 1);
}
}
// Execute loop through by size n
var x: Int = i;
while (x < n)
{
if (visit[x] == 0 && result[j] + collection[x] <= sum)
{
// Active visit status
visit[x] = j + 1;
result[j] = result[j] + collection[x];
if (this.findSolution(collection, result, visit, n, k, sum, i + 1, j) == true)
{
// When solution is found
return true;
}
// Back to previous values
result[j] = result[j] - collection[x];
visit[x] = 0;
}
x += 1;
}
return false;
}
// Handles the request of partition of k with equal sum
fun partition(collection: Array<Int> , n: Int, k: Int): Unit
{
if (k <= 0 || k > n)
{
print("\n Given " + k + " partition not possible\n");
}
else
{
// Loop controlling variable i and j
var i: Int = 0;
var j: Int ;
var sum: Int = 0;
// Sum of elements
while (i < n)
{
sum += collection[i];
i += 1;
}
if (sum % k == 0)
{
// When partition possible of equal sum
// This is used to handle partition sum info
var result: Array <Int> = Array(k)
{
0
};
// This are used to track visited element
var visit: Array<Int> = Array(n)
{
0
};
if (this.findSolution(collection, result, visit, n, k, sum / k, 0, 0) == true)
{
// Display calculated result
print("\n Total Sum : " + sum + "");
print("\n Partition size : " + k + "");
print("\n Equal sum is : " + sum / k + "");
print("\n Output");
print("\n ------------------");
// Display resultant set
j = 1;
while (j <= k)
{
print("\n Set " + j + " : ");
i = 0;
while (i < n)
{
if (visit[i] == j)
{
print(" " + collection[i]);
}
i += 1;
}
j += 1;
}
print("\n\n");
}
else
{
print("\n Partition of size " + k + " cannot be divided into equal amount\n");
}
}
else
{
print("\n Partition with " + k + " parts is not produce equal sum\n");
}
}
}
}
fun main(args: Array <String> ): Unit
{
var task: Subset = Subset();
// Define collection of positive elements
var collection: Array<Int> = arrayOf(6, 2, 7, 1, 8, 4, 5, 3, 9, 15);
// Get the number of elements
var n: Int = collection.count();
// Test cases
var k: Int = 2;
task.partition(collection, n, k);
k = 4;
task.partition(collection, n, k);
k = 3;
task.partition(collection, n, k);
}Output
Total Sum : 60
Partition size : 2
Equal sum is : 30
Output
------------------
Set 1 : 6 2 7 1 5 9
Set 2 : 8 4 3 15
Total Sum : 60
Partition size : 4
Equal sum is : 15
Output
------------------
Set 1 : 6 2 7
Set 2 : 1 5 9
Set 3 : 8 4 3
Set 4 : 15
Total Sum : 60
Partition size : 3
Equal sum is : 20
Output
------------------
Set 1 : 6 2 7 1 4
Set 2 : 8 3 9
Set 3 : 5 15
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