Equal subset sum partition
In this article, we will discuss the problem of equal subset sum partition. Given an array of positive integers, the task is to determine if it can be divided into two subsets with equal sums.
Problem Statement
The problem can be stated as follows: Given an array of integers, we need to find out if it can be partitioned into two subsets such that the sum of elements in both subsets is equal.
Pseudocode Algorithm
Below is the pseudocode algorithm for solving the equal subset sum partition problem:
printArray(arr, n)
for i = 0 to n-1
print arr[i]
partition(arr, n, sum)
create an auxiliary array of size (n + 1) x (sum + 1)
set auxiliary[i][0] = true for 0 <= i <= n
for i = 1 to n
for j = 1 to sum
if arr[i - 1] <= j
auxiliary[i][j] = auxiliary[i - 1][j] or auxiliary[i - 1][j - arr[i - 1]]
else
auxiliary[i][j] = auxiliary[i - 1][j]
return auxiliary[n][sum]
isEqualSumPartition(arr, n)
sum = 0
for i = 0 to n-1
sum += arr[i]
if sum % 2 != 0 or partition(arr, n, sum / 2) == false
print "No"
else
print "Yes"
main()
arr1 = {1, 8, 7, 1, 2, 4, 3}
arr2 = {9, 7, 2, 6}
n = size of arr1
printArray(arr1, n)
isEqualSumPartition(arr1, n)
n = size of arr2
printArray(arr2, n)
isEqualSumPartition(arr2, n)
Code Solution
/*
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
Explanation
The given code uses dynamic programming to solve the equal subset sum partition problem. Here's a step-by-step explanation of the code and its output:
Step 1: Input Arrays
The code declares two arrays:
Array | Elements |
---|---|
arr1 | 1, 8, 7, 1, 2, 4, 3 |
arr2 | 9, 7, 2, 6 |
Step 2: Array Elements
The code prints the elements of each array:
1 8 7 1 2 4 3
Step 3: Check if Equal Subset Sum Partition Exists
The code then checks if an equal subset sum partition exists for each array and prints the result:
Yes
No
Time Complexity
The time complexity of the code is determined by the dynamic programming algorithm used to solve the problem. The nested loops iterate over all elements of the input array and calculate the auxiliary array. Therefore, the time complexity is O(n * sum), where n is the number of elements in the array and sum is the sum of all elements in the array.
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