Equal subset sum partition
Here given code implementation process.
/*
C program for
Equal subset sum partition
*/
#include <stdio.h>
#include <stdbool.h>
// Display array elements
void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
{
printf(" %d", arr[i]);
}
printf("\n");
}
bool partition(int arr[], int n, int sum)
{
// Define auxiliary space which is calculate result
bool auxiliary[n + 1][sum + 1];
// Set default value
for (int i = 0; i <= n; ++i)
{
// Set the value of first column of auxiliary is true
auxiliary[i][0] = true;
// Set default value of other columns
for (int j = 1; j <= sum; ++j)
{
auxiliary[i][j] = false;
}
}
// Outer loop
for (int i = 1; i <= n; ++i)
{
// Inner loop
for (int j = 1; j <= sum; ++j)
{
if (arr[i - 1] <= j)
{
// When i-1 element value is less than j
// Then resultant is based on evalue of auxiliary[i-1][j] or
// auxiliary[i - 1][j - arr[i - 1]]
auxiliary[i][j] = auxiliary[i - 1][j] ||
auxiliary[i - 1][j - arr[i - 1]];
}
else
{
auxiliary[i][j] = auxiliary[i - 1][j];
}
}
}
// Return calculated result
return auxiliary[n][sum];
}
void isEqualSumPartition(int arr[], int n)
{
int sum = 0;
// Calculate the sum of all array elements
for (int i = 0; i < n; ++i)
{
sum += arr[i];
}
if ((sum % 2) != 0 || partition(arr, n, sum / 2) == false)
{
// When sum is not dividing into two equal parts
// And its subset sum is not equal into two part
printf(" No\n");
}
else
{
printf(" Yes\n");
}
}
int main()
{
int arr1[] = {
1 , 8 , 7 , 1 , 2 , 4 , 3
};
int arr2[] = {
9 , 7 , 2 , 6
};
// Case A
// Get the number of elements arr1
int n = sizeof(arr1) / sizeof(arr1[0]);
printArray(arr1, n);
// [8+4+1] == [7+1+3+2]
isEqualSumPartition(arr1, n);
// Case B
// Get the number of elements in arr2
n = sizeof(arr2) / sizeof(arr2[0]);
printArray(arr2, n);
isEqualSumPartition(arr2, n);
return 0;
}
Output
1 8 7 1 2 4 3
Yes
9 7 2 6
No
/*
Java program
Equal subset sum partition
*/
public class EqualSubset
{
// Display array elements
public void printArray(int[] arr, int n)
{
for (int i = 0; i < n; ++i)
{
System.out.print(" " + arr[i] );
}
System.out.print("\n");
}
public boolean partition(int[] arr, int n, int sum)
{
// Define auxiliary space which is calculate result
boolean[][] auxiliary = new boolean[n + 1][sum + 1];
// Set default value
for (int i = 0; i <= n; ++i)
{
// Set the value of first column of auxiliary is true
auxiliary[i][0] = true;
// Set default value of other columns
for (int j = 1; j <= sum; ++j)
{
auxiliary[i][j] = false;
}
}
// Outer loop
for (int i = 1; i <= n; ++i)
{
// Inner loop
for (int j = 1; j <= sum; ++j)
{
if (arr[i - 1] <= j)
{
// When i-1 element value is less than j
// Then resultant is based on evalue of auxiliary[i-1][j] or
// auxiliary[i - 1][j - arr[i - 1]]
auxiliary[i][j] = auxiliary[i - 1][j] ||
auxiliary[i - 1][j - arr[i - 1]];
}
else
{
auxiliary[i][j] = auxiliary[i - 1][j];
}
}
}
// Return calculated result
return auxiliary[n][sum];
}
public void isEqualSumPartition(int[] arr, int n)
{
int sum = 0;
// Calculate the sum of all array elements
for (int i = 0; i < n; ++i)
{
sum += arr[i];
}
if ((sum % 2) != 0 || partition(arr, n, sum / 2) == false)
{
// When sum is not dividing into two equal parts
// And its subset sum is not equal into two part
System.out.print(" No\n");
}
else
{
System.out.print(" Yes\n");
}
}
public static void main(String[] args)
{
EqualSubset task = new EqualSubset();
int[] arr1 = {
1 , 8 , 7 , 1 , 2 , 4 , 3
};
int[] arr2 = {
9 , 7 , 2 , 6
};
// Case A
// Get the number of elements arr1
int n = arr1.length;
task.printArray(arr1, n);
// [8+4+1] == [7+1+3+2]
task.isEqualSumPartition(arr1, n);
// Case B
// Get the number of elements in arr2
n = arr2.length;
task.printArray(arr2, n);
task.isEqualSumPartition(arr2, n);
}
}
Output
1 8 7 1 2 4 3
Yes
9 7 2 6
No
// Include header file
#include <iostream>
using namespace std;
/*
C++ program
Equal subset sum partition
*/
class EqualSubset
{
public:
// Display array elements
void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
{
cout << " " << arr[i];
}
cout << "\n";
}
bool partition(int arr[], int n, int sum)
{
// Define auxiliary space which is calculate result
bool auxiliary[n + 1][sum + 1];
// Set default value
for (int i = 0; i <= n; ++i)
{
// Set the value of first column of auxiliary is true
auxiliary[i][0] = true;
// Set default value of other columns
for (int j = 1; j <= sum; ++j)
{
auxiliary[i][j] = false;
}
}
// Outer loop
for (int i = 1; i <= n; ++i)
{
// Inner loop
for (int j = 1; j <= sum; ++j)
{
if (arr[i - 1] <= j)
{
// When i-1 element value is less than j
// Then resultant is based on evalue of auxiliary[i-1][j] or
// auxiliary[i - 1][j - arr[i - 1]]
auxiliary[i][j] = auxiliary[i - 1][j] ||
auxiliary[i - 1][j - arr[i - 1]];
}
else
{
auxiliary[i][j] = auxiliary[i - 1][j];
}
}
}
// Return calculated result
return auxiliary[n][sum];
}
void isEqualSumPartition(int arr[], int n)
{
int sum = 0;
// Calculate the sum of all array elements
for (int i = 0; i < n; ++i)
{
sum += arr[i];
}
if ((sum % 2) != 0 || this->partition(arr, n, sum / 2) == false)
{
// When sum is not dividing into two equal parts
// And its subset sum is not equal into two part
cout << " No\n";
}
else
{
cout << " Yes\n";
}
}
};
int main()
{
EqualSubset *task = new EqualSubset();
int arr1[] = {
1 , 8 , 7 , 1 , 2 , 4 , 3
};
int arr2[] = {
9 , 7 , 2 , 6
};
// Case A
// Get the number of elements arr1
int n = sizeof(arr1) / sizeof(arr1[0]);
task->printArray(arr1, n);
// [8+4+1] == [7+1+3+2]
task->isEqualSumPartition(arr1, n);
// Case B
// Get the number of elements in arr2
n = sizeof(arr2) / sizeof(arr2[0]);
task->printArray(arr2, n);
task->isEqualSumPartition(arr2, n);
return 0;
}
Output
1 8 7 1 2 4 3
Yes
9 7 2 6
No
// Include namespace system
using System;
/*
Csharp program
Equal subset sum partition
*/
public class EqualSubset
{
// Display array elements
public void printArray(int[] arr, int n)
{
for (int i = 0; i < n; ++i)
{
Console.Write(" " + arr[i]);
}
Console.Write("\n");
}
public Boolean partition(int[] arr, int n, int sum)
{
// Define auxiliary space which is calculate result
Boolean[,] auxiliary = new Boolean[n + 1,sum + 1];
// Set default value
for (int i = 0; i <= n; ++i)
{
// Set the value of first column of auxiliary is true
auxiliary[i,0] = true;
// Set default value of other columns
for (int j = 1; j <= sum; ++j)
{
auxiliary[i,j] = false;
}
}
// Outer loop
for (int i = 1; i <= n; ++i)
{
// Inner loop
for (int j = 1; j <= sum; ++j)
{
if (arr[i - 1] <= j)
{
// When i-1 element value is less than j
// Then resultant is based on evalue of auxiliary[i-1,j] or
// auxiliary[i - 1,j - arr[i - 1]]
auxiliary[i,j] = auxiliary[i - 1,j] ||
auxiliary[i - 1,j - arr[i - 1]];
}
else
{
auxiliary[i,j] = auxiliary[i - 1,j];
}
}
}
// Return calculated result
return auxiliary[n,sum];
}
public void isEqualSumPartition(int[] arr, int n)
{
int sum = 0;
// Calculate the sum of all array elements
for (int i = 0; i < n; ++i)
{
sum += arr[i];
}
if ((sum % 2) != 0 || this.partition(arr, n, sum / 2) == false)
{
// When sum is not dividing into two equal parts
// And its subset sum is not equal into two part
Console.Write(" No\n");
}
else
{
Console.Write(" Yes\n");
}
}
public static void Main(String[] args)
{
EqualSubset task = new EqualSubset();
int[] arr1 = {
1 , 8 , 7 , 1 , 2 , 4 , 3
};
int[] arr2 = {
9 , 7 , 2 , 6
};
// Case A
// Get the number of elements arr1
int n = arr1.Length;
task.printArray(arr1, n);
// [8+4+1] == [7+1+3+2]
task.isEqualSumPartition(arr1, n);
// Case B
// Get the number of elements in arr2
n = arr2.Length;
task.printArray(arr2, n);
task.isEqualSumPartition(arr2, n);
}
}
Output
1 8 7 1 2 4 3
Yes
9 7 2 6
No
package main
import "fmt"
/*
Go program
Equal subset sum partition
*/
// Display array elements
func printArray(arr[] int, n int) {
for i := 0 ; i < n ; i++ {
fmt.Print(" ", arr[i])
}
fmt.Print("\n")
}
func partition(arr[] int, n int, sum int) bool {
// Define auxiliary space which is calculate result
var auxiliary = make([][]bool,n+1);
// Set default value
for i := 0 ; i <= n ; i++ {
auxiliary[i] = make([]bool,sum+1)
// Set the value of first column of auxiliary is true
auxiliary[i][0] = true
}
// Outer loop
for i := 1 ; i <= n ; i++ {
// Inner loop
for j := 1 ; j <= sum ; j++ {
if arr[i - 1] <= j {
// When i-1 element value is less than j
// Then resultant is based on evalue of auxiliary[i-1][j] or
// auxiliary[i - 1][j - arr[i - 1]]
auxiliary[i][j] = auxiliary[i - 1][j] || auxiliary[i - 1][j - arr[i - 1]]
} else {
auxiliary[i][j] = auxiliary[i - 1][j]
}
}
}
// Return calculated result
return auxiliary[n][sum]
}
func isEqualSumPartition(arr[] int, n int) {
var sum int = 0
// Calculate the sum of all array elements
for i := 0 ; i < n ; i++ {
sum += arr[i]
}
if (sum % 2) != 0 || partition(arr, n, sum / 2) == false {
// When sum is not dividing into two equal parts
// And its subset sum is not equal into two part
fmt.Print(" No\n")
} else {
fmt.Print(" Yes\n")
}
}
func main() {
var arr1 = [] int {
1,
8,
7,
1,
2,
4,
3,
}
var arr2 = [] int {
9,
7,
2,
6,
}
// Case A
// Get the number of elements arr1
var n int = len(arr1)
printArray(arr1, n)
// [8+4+1] == [7+1+3+2]
isEqualSumPartition(arr1, n)
// Case B
// Get the number of elements in arr2
n = len(arr2)
printArray(arr2, n)
isEqualSumPartition(arr2, n)
}
Output
1 8 7 1 2 4 3
Yes
9 7 2 6
No
<?php
/*
Php program
Equal subset sum partition
*/
class EqualSubset
{
// Display array elements
public function printArray($arr, $n)
{
for ($i = 0; $i < $n; ++$i)
{
echo(" ".$arr[$i]);
}
echo("\n");
}
public function partition($arr, $n, $sum)
{
// Define auxiliary space which is calculate result
$auxiliary = array_fill(0, $n + 1, array_fill(0,$sum + 1, false));
// Set default value
for ($i = 0; $i <= $n; ++$i)
{
// Set the value of first column of auxiliary is true
$auxiliary[$i][0] = true;
}
// Outer loop
for ($i = 1; $i <= $n; ++$i)
{
// Inner loop
for ($j = 1; $j <= $sum; ++$j)
{
if ($arr[$i - 1] <= $j)
{
// When i-1 element value is less than j
// Then resultant is based on evalue of auxiliary[i-1][j] or
// auxiliary[i - 1][j - arr[i - 1]]
$auxiliary[$i][$j] = $auxiliary[$i - 1][$j] || $auxiliary[$i - 1][$j - $arr[$i - 1]];
}
else
{
$auxiliary[$i][$j] = $auxiliary[$i - 1][$j];
}
}
}
// Return calculated result
return $auxiliary[$n][$sum];
}
public function isEqualSumPartition($arr, $n)
{
$sum = 0;
// Calculate the sum of all array elements
for ($i = 0; $i < $n; ++$i)
{
$sum += $arr[$i];
}
if (($sum % 2) != 0 || $this->partition($arr, $n, (int)($sum / 2)) == false)
{
// When sum is not dividing into two equal parts
// And its subset sum is not equal into two part
echo(" No\n");
}
else
{
echo(" Yes\n");
}
}
}
function main()
{
$task = new EqualSubset();
$arr1 = array(1, 8, 7, 1, 2, 4, 3);
$arr2 = array(9, 7, 2, 6);
// Case A
// Get the number of elements arr1
$n = count($arr1);
$task->printArray($arr1, $n);
// [8+4+1] == [7+1+3+2]
$task->isEqualSumPartition($arr1, $n);
// Case B
// Get the number of elements in arr2
$n = count($arr2);
$task->printArray($arr2, $n);
$task->isEqualSumPartition($arr2, $n);
}
main();
Output
1 8 7 1 2 4 3
Yes
9 7 2 6
No
/*
Node JS program
Equal subset sum partition
*/
class EqualSubset
{
// Display array elements
printArray(arr, n)
{
for (var i = 0; i < n; ++i)
{
process.stdout.write(" " + arr[i]);
}
process.stdout.write("\n");
}
partition(arr, n, sum)
{
// Define auxiliary space which is calculate result
var auxiliary = Array(n + 1).fill(false).map(() =>
new Array(sum + 1).fill(false));
// Set default value
for (var i = 0; i <= n; ++i)
{
// Set the value of first column of auxiliary is true
auxiliary[i][0] = true;
}
// Outer loop
for (var i = 1; i <= n; ++i)
{
// Inner loop
for (var j = 1; j <= sum; ++j)
{
if (arr[i - 1] <= j)
{
// When i-1 element value is less than j
// Then resultant is based on evalue of auxiliary[i-1][j] or
// auxiliary[i - 1][j - arr[i - 1]]
auxiliary[i][j] = auxiliary[i - 1][j] ||
auxiliary[i - 1][j - arr[i - 1]];
}
else
{
auxiliary[i][j] = auxiliary[i - 1][j];
}
}
}
// Return calculated result
return auxiliary[n][sum];
}
isEqualSumPartition(arr, n)
{
var sum = 0;
// Calculate the sum of all array elements
for (var i = 0; i < n; ++i)
{
sum += arr[i];
}
if ((sum % 2) != 0 || this.partition(arr, n, parseInt(sum / 2)) == false)
{
// When sum is not dividing into two equal parts
// And its subset sum is not equal into two part
process.stdout.write(" No\n");
}
else
{
process.stdout.write(" Yes\n");
}
}
}
function main()
{
var task = new EqualSubset();
var arr1 = [1, 8, 7, 1, 2, 4, 3];
var arr2 = [9, 7, 2, 6];
// Case A
// Get the number of elements arr1
var n = arr1.length;
task.printArray(arr1, n);
// [8+4+1] == [7+1+3+2]
task.isEqualSumPartition(arr1, n);
// Case B
// Get the number of elements in arr2
n = arr2.length;
task.printArray(arr2, n);
task.isEqualSumPartition(arr2, n);
}
main();
Output
1 8 7 1 2 4 3
Yes
9 7 2 6
No
# Python 3 program
# Equal subset sum partition
class EqualSubset :
# Display list elements
def printArray(self, arr, n) :
i = 0
while (i < n) :
print(" ", arr[i], end = "")
i += 1
print(end = "\n")
def partition(self, arr, n, sum) :
# Define auxiliary space which is calculate result
auxiliary = [[False] * (sum + 1) for _ in range(n + 1) ]
i = 0
# Set default value
while (i <= n) :
# Set the value of first column of auxiliary is true
auxiliary[i][0] = True
i += 1
i = 1
# Outer loop
while (i <= n) :
j = 1
# Inner loop
while (j <= sum) :
if (arr[i - 1] <= j) :
# When i-1 element value is less than j
# Then resultant is based on evalue of auxiliary[i-1][j] or
# auxiliary[i - 1][j - arr[i - 1]]
auxiliary[i][j] = auxiliary[i - 1][j] or auxiliary[i - 1][j - arr[i - 1]]
else :
auxiliary[i][j] = auxiliary[i - 1][j]
j += 1
i += 1
# Return calculated result
return auxiliary[n][sum]
def isEqualSumPartition(self, arr, n) :
sum = 0
i = 0
# Calculate the sum of all list elements
while (i < n) :
sum += arr[i]
i += 1
if ((sum % 2) != 0 or
self.partition(arr, n, int(sum / 2)) == False) :
# When sum is not dividing into two equal parts
# And its subset sum is not equal into two part
print(" No")
else :
print(" Yes")
def main() :
task = EqualSubset()
arr1 = [1, 8, 7, 1, 2, 4, 3]
arr2 = [9, 7, 2, 6]
# Case A
# Get the number of elements arr1
n = len(arr1)
task.printArray(arr1, n)
# [8+4+1] == [7+1+3+2]
task.isEqualSumPartition(arr1, n)
# Case B
# Get the number of elements in arr2
n = len(arr2)
task.printArray(arr2, n)
task.isEqualSumPartition(arr2, n)
if __name__ == "__main__": main()
Output
1 8 7 1 2 4 3
Yes
9 7 2 6
No
# Ruby program
# Equal subset sum partition
class EqualSubset
# Display array elements
def printArray(arr, n)
i = 0
while (i < n)
print(" ", arr[i])
i += 1
end
print("\n")
end
def partition(arr, n, sum)
# Define auxiliary space which is calculate result
auxiliary = Array.new(n + 1) {Array.new(sum + 1) {false}}
i = 0
# Set default value
while (i <= n)
# Set the value of first column of auxiliary is true
auxiliary[i][0] = true
i += 1
end
i = 1
# Outer loop
while (i <= n)
j = 1
# Inner loop
while (j <= sum)
if (arr[i - 1] <= j)
# When i-1 element value is less than j
# Then resultant is based on evalue of auxiliary[i-1][j] or
# auxiliary[i - 1][j - arr[i - 1]]
auxiliary[i][j] = auxiliary[i - 1][j] ||
auxiliary[i - 1][j - arr[i - 1]]
else
auxiliary[i][j] = auxiliary[i - 1][j]
end
j += 1
end
i += 1
end
# Return calculated result
return auxiliary[n][sum]
end
def isEqualSumPartition(arr, n)
sum = 0
i = 0
# Calculate the sum of all array elements
while (i < n)
sum += arr[i]
i += 1
end
if ((sum % 2) != 0 || self.partition(arr, n, sum / 2) == false)
# When sum is not dividing into two equal parts
# And its subset sum is not equal into two part
print(" No\n")
else
print(" Yes\n")
end
end
end
def main()
task = EqualSubset.new()
arr1 = [1, 8, 7, 1, 2, 4, 3]
arr2 = [9, 7, 2, 6]
# Case A
# Get the number of elements arr1
n = arr1.length
task.printArray(arr1, n)
# [8+4+1] == [7+1+3+2]
task.isEqualSumPartition(arr1, n)
# Case B
# Get the number of elements in arr2
n = arr2.length
task.printArray(arr2, n)
task.isEqualSumPartition(arr2, n)
end
main()
Output
1 8 7 1 2 4 3
Yes
9 7 2 6
No
/*
Scala program
Equal subset sum partition
*/
class EqualSubset()
{
// Display array elements
def printArray(arr: Array[Int], n: Int): Unit = {
var i: Int = 0;
while (i < n)
{
print(" " + arr(i));
i += 1;
}
print("\n");
}
def partition(arr: Array[Int], n: Int, sum: Int): Boolean = {
// Define auxiliary space which is calculate result
var auxiliary: Array[Array[Boolean]] =
Array.fill[Boolean](n + 1, sum + 1)(false);
var i: Int = 0;
// Set default value
while (i <= n)
{
// Set the value of first column of auxiliary is true
auxiliary(i)(0) = true;
i += 1;
}
i = 1;
// Outer loop
while (i <= n)
{
var j = 1;
// Inner loop
while (j <= sum)
{
if (arr(i - 1) <= j)
{
// When i-1 element value is less than j
// Then resultant is based on evalue of auxiliary[i-1][j] or
// auxiliary[i - 1][j - arr[i - 1]]
auxiliary(i)(j) = auxiliary(i - 1)(j) ||
auxiliary(i - 1)(j - arr(i - 1));
}
else
{
auxiliary(i)(j) = auxiliary(i - 1)(j);
}
j += 1;
}
i += 1;
}
// Return calculated result
return auxiliary(n)(sum);
}
def isEqualSumPartition(arr: Array[Int], n: Int): Unit = {
var sum: Int = 0;
var i: Int = 0;
// Calculate the sum of all array elements
while (i < n)
{
sum += arr(i);
i += 1;
}
if ((sum % 2) != 0 || partition(arr, n, sum / 2) == false)
{
// When sum is not dividing into two equal parts
// And its subset sum is not equal into two part
print(" No\n");
}
else
{
print(" Yes\n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: EqualSubset = new EqualSubset();
var arr1: Array[Int] = Array(1, 8, 7, 1, 2, 4, 3);
var arr2: Array[Int] = Array(9, 7, 2, 6);
// Case A
// Get the number of elements arr1
var n: Int = arr1.length;
task.printArray(arr1, n);
// [8+4+1] == [7+1+3+2]
task.isEqualSumPartition(arr1, n);
// Case B
// Get the number of elements in arr2
n = arr2.length;
task.printArray(arr2, n);
task.isEqualSumPartition(arr2, n);
}
}
Output
1 8 7 1 2 4 3
Yes
9 7 2 6
No
import Foundation;
/*
Swift 4 program
Equal subset sum partition
*/
class EqualSubset
{
// Display array elements
func printArray(_ arr: [Int], _ n: Int)
{
var i: Int = 0;
while (i < n)
{
print(" ", arr[i], terminator: "");
i += 1;
}
print(terminator: "\n");
}
func partition(_ arr: [Int], _ n: Int, _ sum: Int) -> Bool
{
// Define auxiliary space which is calculate result
var auxiliary: [
[Bool]
] = Array(repeating: Array(repeating: false, count: sum + 1),
count: n + 1);
var i: Int = 0;
// Set default value
while (i <= n)
{
// Set the value of first column of auxiliary is true
auxiliary[i][0] = true;
i += 1;
}
i = 1;
// Outer loop
while (i <= n)
{
var j: Int = 1;
// Inner loop
while (j <= sum)
{
if (arr[i - 1] <= j)
{
// When i-1 element value is less than j
// Then resultant is based on evalue of auxiliary[i-1][j] or
// auxiliary[i - 1][j - arr[i - 1]]
auxiliary[i][j] = auxiliary[i - 1][j] ||
auxiliary[i - 1][j - arr[i - 1]];
}
else
{
auxiliary[i][j] = auxiliary[i - 1][j];
}
j += 1;
}
i += 1;
}
// Return calculated result
return auxiliary[n][sum];
}
func isEqualSumPartition(_ arr: [Int], _ n: Int)
{
var sum: Int = 0;
var i: Int = 0;
// Calculate the sum of all array elements
while (i < n)
{
sum += arr[i];
i += 1;
}
if ((sum % 2) != 0 || self.partition(arr, n, sum / 2) == false)
{
// When sum is not dividing into two equal parts
// And its subset sum is not equal into two part
print(" No");
}
else
{
print(" Yes");
}
}
}
func main()
{
let task: EqualSubset = EqualSubset();
let arr1: [Int] = [1, 8, 7, 1, 2, 4, 3];
let arr2: [Int] = [9, 7, 2, 6];
// Case A
// Get the number of elements arr1
var n: Int = arr1.count;
task.printArray(arr1, n);
// [8+4+1] == [7+1+3+2]
task.isEqualSumPartition(arr1, n);
// Case B
// Get the number of elements in arr2
n = arr2.count;
task.printArray(arr2, n);
task.isEqualSumPartition(arr2, n);
}
main();
Output
1 8 7 1 2 4 3
Yes
9 7 2 6
No
/*
Kotlin program
Equal subset sum partition
*/
class EqualSubset
{
// Display array elements
fun printArray(arr: Array < Int > , n: Int): Unit
{
var i: Int = 0;
while (i < n)
{
print(" " + arr[i]);
i += 1;
}
print("\n");
}
fun partition(arr: Array < Int > , n: Int, sum: Int): Boolean
{
// Define auxiliary space which is calculate result
val auxiliary: Array < Array < Boolean >> = Array(n + 1)
{
Array(sum + 1)
{
false
}
};
var i: Int = 0;
// Set default value
while (i <= n)
{
// Set the value of first column of auxiliary is true
auxiliary[i][0] = true;
i += 1;
}
i = 1;
// Outer loop
while (i <= n)
{
var j: Int = 1;
// Inner loop
while (j <= sum)
{
if (arr[i - 1] <= j)
{
// When i-1 element value is less than j
// Then resultant is based on evalue of auxiliary[i-1][j] or
// auxiliary[i - 1][j - arr[i - 1]]
auxiliary[i][j] = auxiliary[i - 1][j] ||
auxiliary[i - 1][j - arr[i - 1]];
}
else
{
auxiliary[i][j] = auxiliary[i - 1][j];
}
j += 1;
}
i += 1;
}
// Return calculated result
return auxiliary[n][sum];
}
fun isEqualSumPartition(arr: Array < Int > , n: Int): Unit
{
var sum: Int = 0;
var i: Int = 0;
// Calculate the sum of all array elements
while (i < n)
{
sum += arr[i];
i += 1;
}
if ((sum % 2) != 0 || this.partition(arr, n, sum / 2) == false)
{
// When sum is not dividing into two equal parts
// And its subset sum is not equal into two part
print(" No\n");
}
else
{
print(" Yes\n");
}
}
}
fun main(args: Array < String > ): Unit
{
val task: EqualSubset = EqualSubset();
val arr1: Array < Int > = arrayOf(1, 8, 7, 1, 2, 4, 3);
val arr2: Array < Int > = arrayOf(9, 7, 2, 6);
// Case A
// Get the number of elements arr1
var n: Int = arr1.count();
task.printArray(arr1, n);
// [8+4+1] == [7+1+3+2]
task.isEqualSumPartition(arr1, n);
// Case B
// Get the number of elements in arr2
n = arr2.count();
task.printArray(arr2, n);
task.isEqualSumPartition(arr2, n);
}
Output
1 8 7 1 2 4 3
Yes
9 7 2 6
No
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