Posted on by Kalkicode
Code Greedy

Find sum of all subsets of a given array

This article discusses the problem of finding the sum of all subsets of a given array. The goal is to calculate the sum of all possible subsets, including the empty subset. We'll explain the problem statement, provide a pseudocode algorithm with explanations, and discuss the resulting output. The time complexity of the code will also be analyzed.

Problem Statement

Given an array of integers, we need to find the sum of all subsets. A subset is any combination of elements from the array. For example, if we have an array [1, 2, 3], the subsets would be [], [1], [2], [3], [1, 2], [1, 3], and [1, 2, 3]. We need to calculate the sum of all these subsets.

Pseudocode Algorithm

Here's the pseudocode algorithm for finding the sum of all subsets of a given array:


subsetSum(arr, size, i, n, sum):
	if i == size:
		return sum * (1 << (n - 1))
	result = subsetSum(arr, size, i + 1, n, sum)
	result += subsetSum(arr, size, i + 1, n + 1, sum + arr[i])
	return result

Let's understand the algorithm step by step:

  • subsetSum is a recursive function that takes the array arr, its size size, the current index i, the number of elements in the subset n, and the current sum sum as parameters.
  • If the index i reaches the size of the array, it means we have considered all the elements. In this case, we return the product of the current sum and 2^(n - 1), where ^ represents exponentiation. This calculation accounts for subsets with different multiples.
  • Otherwise, we recursively call the subsetSum function twice:
    • The first call doesn't include the current element in the subset, so we keep the same sum and number of elements.
    • The second call includes the current element in the subset, so we increment the sum by the current element and increase the number of elements by 1.
    We add the results of these two recursive calls and return the final result.

Code Solution

/*
    C Program 
    Find sum of all subsets of a given array
*/
#include <stdio.h>

void printData(int arr[],int size)
{
    printf("\n Array elements \n");
    for (int i = 0; i < size; ++i)
    {
        printf(" %d",arr[i]);
    }
    printf("\n");
}
// Return sum of all subsets
int subsetSum(int arr[],int size, int i, int n, int sum)
{
   
    if(i==size)
    {
        // Here ( n -1) is indicates subset sum with different multiples
        return sum * (1 << (n-1));
    }

    // Get the subset sum
    int result = subsetSum(arr,size,i+1,n,sum);
    result    += subsetSum(arr,size,i+1,n+1, sum+arr[i]);

    // Return calculated result
    return result;
}
int main(int argc, char const *argv[])
{
    int arr1[] = { 1,2,3,4,5 }; 
    int arr2[] = { 1,4,5 }; 
    // Get the number of element in array
    int size = sizeof(arr1)/sizeof(arr1[0]); 

    printData(arr1,size);

    // Find sum of existing subset
    int sum = subsetSum(arr1,size,0,0,0); 
    printf(" Sumset Sum is : %d\n",sum); 


    size = sizeof(arr2)/sizeof(arr2[0]); 
    printData(arr2,size);
    // Find sum of existing subset
    sum = subsetSum(arr2,size,0,0,0); 
    printf(" Sumset Sum is : %d\n",sum); 

    return 0;
}

Output

 Array elements
 1 2 3 4 5
 Sumset Sum is : 1215

 Array elements
 1 4 5
 Sumset Sum is : 90
/*
  Java program
  Find sum of all subsets of a given array
*/
class Subsets
{
	// Display array elements
	public void printData(int[] arr, int size)
	{
		System.out.print("\n Array elements \n");
		for (int i = 0; i < size; ++i)
		{
			System.out.print(" " + arr[i]);
		}
		System.out.print("\n");
	}
	// Return sum of all subsets
	public int subsetSum(int[] arr, int size, int i, int n, int sum)
	{
		if (i == size)
		{
			// Here ( n -1) is indicates subset sum with different multiples
			return sum * (1 << (n - 1));
		}
		// Get the subset sum
		int result = subsetSum(arr, size, i + 1, n, sum);
		result += subsetSum(arr, size, i + 1, n + 1, sum + arr[i]);
		// Return calculated result
		return result;
	}
	public static void main(String[] args)
	{
		Subsets task = new Subsets();
		int[] arr1 = {
			1 , 2 , 3 , 4 , 5
		};
		int[] arr2 = {
			1 , 4 , 5
		};
		// Get the number of element in arr1
		int size = arr1.length;
		task.printData(arr1, size);
		// Find sum of existing subset
		int sum = task.subsetSum(arr1, size, 0, 0, 0);
		System.out.print(" Sumset Sum is : " + sum + "\n");
		// Get the size of arr2
		size = arr2.length;
		task.printData(arr2, size);
		// Find sum of existing subset
		sum = task.subsetSum(arr2, size, 0, 0, 0);
		System.out.print(" Sumset Sum is : " + sum + "\n");
	}
}

Output

 Array elements
 1 2 3 4 5
 Sumset Sum is : 1215

 Array elements
 1 4 5
 Sumset Sum is : 90
// Include header file
#include <iostream>

using namespace std;
/*
  C++ program
  Find sum of all subsets of a given array
*/
class Subsets
{
	public:
		// Display array elements
		void printData(int arr[], int size)
		{
			cout << "\n Array elements \n";
			for (int i = 0; i < size; ++i)
			{
				cout << " " << arr[i];
			}
			cout << "\n";
		}
	// Return sum of all subsets
	int subsetSum(int arr[], int size, int i, int n, int sum)
	{
		// Return calculated result
		if (i == size)
		{
			// Here ( n -1) is indicates subset sum with different multiples
			return sum *(1 << (n - 1));
		}
		// Get the subset sum
		int result = this->subsetSum(arr, size, i + 1, n, sum);
		result += this->subsetSum(arr, size, i + 1, n + 1, sum + arr[i]);
		return result;
	}
};
int main()
{
	Subsets task = Subsets();
	int arr1[] = {
		1 , 2 , 3 , 4 , 5
	};
	int arr2[] = {
		1 , 4 , 5
	};
	// Get the number of element in arr1
	int size = sizeof(arr1) / sizeof(arr1[0]);
	task.printData(arr1, size);
	// Find sum of existing subset
	int sum = task.subsetSum(arr1, size, 0, 0, 0);
	cout << " Sumset Sum is : " << sum << "\n";
	// Get the size of arr2
	size = sizeof(arr2) / sizeof(arr2[0]);
	task.printData(arr2, size);
	// Find sum of existing subset
	sum = task.subsetSum(arr2, size, 0, 0, 0);
	cout << " Sumset Sum is : " << sum << "\n";
	return 0;
}

Output

 Array elements
 1 2 3 4 5
 Sumset Sum is : 1215

 Array elements
 1 4 5
 Sumset Sum is : 90
// Include namespace system
using System;
/*
  C# program
  Find sum of all subsets of a given array
*/
public class Subsets
{
	// Display array elements
	public void printData(int[] arr, int size)
	{
		Console.Write("\n Array elements \n");
		for (int i = 0; i < size; ++i)
		{
			Console.Write(" " + arr[i]);
		}
		Console.Write("\n");
	}
	// Return sum of all subsets
	public int subsetSum(int[] arr, int size, int i, int n, int sum)
	{
		// Return calculated result
		if (i == size)
		{
			// Here ( n -1) is indicates subset sum with different multiples
			return sum * (1 << (n - 1));
		}
		// Get the subset sum
		int result = subsetSum(arr, size, i + 1, n, sum);
		result += subsetSum(arr, size, i + 1, n + 1, sum + arr[i]);
		return result;
	}
	public static void Main(String[] args)
	{
		Subsets task = new Subsets();
		int[] arr1 = {
			1 , 2 , 3 , 4 , 5
		};
		int[] arr2 = {
			1 , 4 , 5
		};
		// Get the number of element in arr1
		int size = arr1.Length;
		task.printData(arr1, size);
		// Find sum of existing subset
		int sum = task.subsetSum(arr1, size, 0, 0, 0);
		Console.Write(" Sumset Sum is : " + sum + "\n");
		// Get the size of arr2
		size = arr2.Length;
		task.printData(arr2, size);
		// Find sum of existing subset
		sum = task.subsetSum(arr2, size, 0, 0, 0);
		Console.Write(" Sumset Sum is : " + sum + "\n");
	}
}

Output

 Array elements
 1 2 3 4 5
 Sumset Sum is : 1215

 Array elements
 1 4 5
 Sumset Sum is : 90
<?php
/*
  Php program
  Find sum of all subsets of a given array
*/
class Subsets
{
	// Display array elements
	public	function printData( & $arr, $size)
	{
		echo "\n Array elements \n";
		for ($i = 0; $i < $size; ++$i)
		{
			echo " ". $arr[$i];
		}
		echo "\n";
	}
	// Return sum of all subsets
	public	function subsetSum( & $arr, $size, $i, $n, $sum)
	{
		// Return calculated result
		if ($i == $size)
		{
			// Here ( n -1) is indicates subset sum with different multiples
			return $sum * (1 << ($n - 1));
		}
		// Get the subset sum
		$result = $this->subsetSum($arr, $size, $i + 1, $n, $sum);
		$result += $this->subsetSum($arr, $size, $i + 1, $n + 1, $sum + $arr[$i]);
		return $result;
	}
}

function main()
{
	$task = new Subsets();
	$arr1 = array(1, 2, 3, 4, 5);
	$arr2 = array(1, 4, 5);
	// Get the number of element in arr1
	$size = count($arr1);
	$task->printData($arr1, $size);
	// Find sum of existing subset
	$sum = $task->subsetSum($arr1, $size, 0, 0, 0);
	echo " Sumset Sum is : ". $sum ."\n";
	// Get the size of arr2
	$size = count($arr2);
	$task->printData($arr2, $size);
	// Find sum of existing subset
	$sum = $task->subsetSum($arr2, $size, 0, 0, 0);
	echo " Sumset Sum is : ". $sum ."\n";
}
main();

Output

 Array elements
 1 2 3 4 5
 Sumset Sum is : 1215

 Array elements
 1 4 5
 Sumset Sum is : 90
/*
  Node Js program
  Find sum of all subsets of a given array
*/
class Subsets
{
	// Display array elements
	printData(arr, size)
	{
		process.stdout.write("\n Array elements \n");
		for (var i = 0; i < size; ++i)
		{
			process.stdout.write(" " + arr[i]);
		}
		process.stdout.write("\n");
	}
	// Return sum of all subsets
	subsetSum(arr, size, i, n, sum)
	{
		// Return calculated result
		if (i == size)
		{
			// Here ( n -1) is indicates subset sum with different multiples
			return sum * (1 << (n - 1));
		}
		// Get the subset sum
		var result = this.subsetSum(arr, size, i + 1, n, sum);
		result += this.subsetSum(arr, size, i + 1, n + 1, sum + arr[i]);
		return result;
	}
}

function main()
{
	var task = new Subsets();
	var arr1 = [1, 2, 3, 4, 5];
	var arr2 = [1, 4, 5];
	// Get the number of element in arr1
	var size = arr1.length;
	task.printData(arr1, size);
	// Find sum of existing subset
	var sum = task.subsetSum(arr1, size, 0, 0, 0);
	process.stdout.write(" Sumset Sum is : " + sum + "\n");
	// Get the size of arr2
	size = arr2.length;
	task.printData(arr2, size);
	// Find sum of existing subset
	sum = task.subsetSum(arr2, size, 0, 0, 0);
	process.stdout.write(" Sumset Sum is : " + sum + "\n");
}
main();

Output

 Array elements
 1 2 3 4 5
 Sumset Sum is : 1215

 Array elements
 1 4 5
 Sumset Sum is : 90
#   Python 3 program
#   Find sum of all subsets of a given array

class Subsets :
    #  Display array elements
    def printData(self, arr, size) :
        print("\n Array elements ")
        i = 0
        while (i < size) :
            print(" ", arr[i], end = "")
            i += 1
        
        print(end = "\n")
    
    #  Return sum of all subsets
    def subsetSum(self, arr, size, i, n, sum) :
        #  Return calculated result
        if (i == size) :
            #  Here ( n -1) is indicates subset sum with different multiples
            if(n > 1) :
                return sum * (1 << (n - 1))
            return sum
        
        #  Get the subset sum
        result = self.subsetSum(arr, size, i + 1, n, sum)
        result += self.subsetSum(arr, size, i + 1, n + 1, sum + arr[i])
        return result
    

def main() :
    task = Subsets()
    arr1 = [1, 2, 3, 4, 5]
    arr2 = [1, 4, 5]
    #  Get the number of element in arr1
    size = len(arr1)
    task.printData(arr1, size)
    #  Find sum of existing subset
    sum = task.subsetSum(arr1, size, 0, 0, 0)
    print(" Sumset Sum is : ", sum )
    #  Get the size of arr2
    size = len(arr2)
    task.printData(arr2, size)
    #  Find sum of existing subset
    sum = task.subsetSum(arr2, size, 0, 0, 0)
    print(" Sumset Sum is : ", sum )

if __name__ == "__main__": main()

Output

 Array elements
  1  2  3  4  5
 Sumset Sum is :  1215

 Array elements
  1  4  5
 Sumset Sum is :  90
#   Ruby program
#   Find sum of all subsets of a given array

class Subsets 
	#  Display array elements
	def printData(arr, size) 
		print("\n Array elements \n")
		i = 0
		while (i < size) 
			print(" ", arr[i])
			i += 1
		end

		print("\n")
	end

	#  Return sum of all subsets
	def subsetSum(arr, size, i, n, sum) 
		#  Return calculated result
		if (i == size) 
			#  Here ( n -1) is indicates subset sum with different multiples
			return sum * (1 << (n - 1))
		end

		#  Get the subset sum
		result = self.subsetSum(arr, size, i + 1, n, sum)
		result += self.subsetSum(arr, size, i + 1, n + 1, sum + arr[i])
		return result
	end

end

def main() 
	task = Subsets.new()
	arr1 = [1, 2, 3, 4, 5]
	arr2 = [1, 4, 5]
	#  Get the number of element in arr1
	size = arr1.length
	task.printData(arr1, size)
	#  Find sum of existing subset
	sum = task.subsetSum(arr1, size, 0, 0, 0)
	print(" Sumset Sum is : ", sum ,"\n")
	#  Get the size of arr2
	size = arr2.length
	task.printData(arr2, size)
	#  Find sum of existing subset
	sum = task.subsetSum(arr2, size, 0, 0, 0)
	print(" Sumset Sum is : ", sum ,"\n")
end

main()

Output

 Array elements 
 1 2 3 4 5
 Sumset Sum is : 1215

 Array elements 
 1 4 5
 Sumset Sum is : 90
/*
  Scala program
  Find sum of all subsets of a given array
*/
class Subsets
{
	// Display array elements
	def printData(arr: Array[Int], size: Int): Unit = {
		print("\n Array elements \n");
		var i: Int = 0;
		while (i < size)
		{
			print(" " + arr(i));
			i += 1;
		}
		print("\n");
	}
	// Return sum of all subsets
	def subsetSum(arr: Array[Int], size: Int, i: Int, n: Int, sum: Int): Int = {
		// Return calculated result
		if (i == size)
		{
			// Here ( n -1) is indicates subset sum with different multiples
			return sum * (1 << (n - 1));
		}
		// Get the subset sum
		var result: Int = this.subsetSum(arr, size, i + 1, n, sum);
		result += this.subsetSum(arr, size, i + 1, n + 1, sum + arr(i));
		return result;
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Subsets = new Subsets();
		var arr1: Array[Int] = Array(1, 2, 3, 4, 5);
		var arr2: Array[Int] = Array(1, 4, 5);
		// Get the number of element in arr1
		var size: Int = arr1.length;
		task.printData(arr1, size);
		// Find sum of existing subset
		var sum: Int = task.subsetSum(arr1, size, 0, 0, 0);
		print(" Sumset Sum is : " + sum + "\n");
		// Get the size of arr2
		size = arr2.length;
		task.printData(arr2, size);
		// Find sum of existing subset
		sum = task.subsetSum(arr2, size, 0, 0, 0);
		print(" Sumset Sum is : " + sum + "\n");
	}
}

Output

 Array elements
 1 2 3 4 5
 Sumset Sum is : 1215

 Array elements
 1 4 5
 Sumset Sum is : 90
/*
  Swift 4 program
  Find sum of all subsets of a given array
*/
class Subsets
{
	// Display array elements
	func printData(_ arr: [Int], _ size: Int)
	{
		print("\n Array elements ");
		var i: Int = 0;
		while (i < size)
		{
			print(" ", arr[i], terminator: "");
			i += 1;
		}
		print(terminator: "\n");
	}
	// Return sum of all subsets
	func subsetSum(_ arr: [Int], _ size: Int, _ i: Int, _ n: Int, _ sum: Int)->Int
	{
		// Return calculated result
		if (i == size)
		{
			// Here ( n -1) is indicates subset sum with different multiples
			return sum * (1 << (n - 1));
		}
		// Get the subset sum
		var result: Int = self.subsetSum(arr, size, i + 1, n, sum);
		result += self.subsetSum(arr, size, i + 1, n + 1, sum + arr[i]);
		return result;
	}
}
func main()
{
	let task: Subsets = Subsets();
	let arr1: [Int] = [1, 2, 3, 4, 5];
	let arr2: [Int] = [1, 4, 5];
	// Get the number of element in arr1
	var size: Int = arr1.count;
	task.printData(arr1, size);
	// Find sum of existing subset
	var sum: Int = task.subsetSum(arr1, size, 0, 0, 0);
	print(" Sumset Sum is : ", sum );
	// Get the size of arr2
	size = arr2.count;
	task.printData(arr2, size);
	// Find sum of existing subset
	sum = task.subsetSum(arr2, size, 0, 0, 0);
	print(" Sumset Sum is : ", sum );
}
main();

Output

 Array elements
  1  2  3  4  5
 Sumset Sum is :  1215

 Array elements
  1  4  5
 Sumset Sum is :  90
/*
  Kotlin program
  Find sum of all subsets of a given array
*/
class Subsets
{
	// Display array elements
	fun printData(arr: Array <Int> , size: Int): Unit
	{
		print("\n Array elements \n");
		var i: Int = 0;
		while (i < size)
		{
			print(" " + arr[i]);
			i += 1;
		}
		print("\n");
	}
	// Return sum of all subsets
	fun subsetSum(arr: Array <Int> , size: Int, i: Int, n: Int, sum: Int): Int
	{
		// Return calculated result
		if (i == size)
		{
			// Here ( n -1) is indicates subset sum with different multiples
			return sum * (1 shl (n - 1));
		}
		// Get the subset sum
		var result: Int = this.subsetSum(arr, size, i + 1, n, sum);
		result += this.subsetSum(arr, size, i + 1, n + 1, sum + arr[i]);
		return result;
	}
}
fun main(args: Array < String > ): Unit
{
	var task: Subsets = Subsets();
	var arr1: Array < Int > = arrayOf(1, 2, 3, 4, 5);
	var arr2: Array < Int > = arrayOf(1, 4, 5);
	// Get the number of element in arr1
	var size: Int = arr1.count();
	task.printData(arr1, size);
	// Find sum of existing subset
	var sum: Int = task.subsetSum(arr1, size, 0, 0, 0);
	print(" Sumset Sum is : " + sum + "\n");
	// Get the size of arr2
	size = arr2.count();
	task.printData(arr2, size);
	// Find sum of existing subset
	sum = task.subsetSum(arr2, size, 0, 0, 0);
	print(" Sumset Sum is : " + sum + "\n");
}

Output

 Array elements
 1 2 3 4 5
 Sumset Sum is : 1215

 Array elements
 1 4 5
 Sumset Sum is : 90

Resultant Output Explanation

Let's analyze the output generated by the given code for two example arrays: [1, 2, 3, 4, 5] and [1, 4, 5].

    
        Array elements
        1 2 3 4 5
        Sumset Sum is : 1215
    

The output for the first array shows that the sum of all its subsets is 1215.

    
        Array elements
        1 4 5
        Sumset Sum is : 90
    

The output for the second array indicates that the sum of all its subsets is 90.

Time Complexity

The time complexity of the algorithm can be analyzed as follows:

  • The recursive function subsetSum is called twice at each level of recursion.
  • The recursion depth is equal to the size of the array.
  • Therefore, the time complexity can be approximated as O(2^n), where n is the size of the array.

Finally

In this article, we discussed the problem of finding the sum of all subsets of a given array. We provided a detailed explanation of the problem statement, presented a pseudocode algorithm with step-by-step explanations, and analyzed the resultant output. Additionally, we discussed the time complexity of the code. By implementing this algorithm, you can find the sum of all subsets of an array efficiently.

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