Posted on by Kalkicode
Code Dynamic Programming

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.

Comment

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

New Comment





Categories
Relative Post