# 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], [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);

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);
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)
{
int[] arr1 = {
1 , 2 , 3 , 4 , 5
};
int[] arr2 = {
1 , 4 , 5
};
// Get the number of element in arr1
int size = arr1.length;
// 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;
// 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()
{
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);
// 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);
// 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)
{
int[] arr1 = {
1 , 2 , 3 , 4 , 5
};
int[] arr2 = {
1 , 4 , 5
};
// Get the number of element in arr1
int size = arr1.Length;
// 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;
// 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()
{
\$arr1 = array(1, 2, 3, 4, 5);
\$arr2 = array(1, 4, 5);
// Get the number of element in arr1
\$size = count(\$arr1);
// 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);
// 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 arr1 = [1, 2, 3, 4, 5];
var arr2 = [1, 4, 5];
// Get the number of element in arr1
var size = arr1.length;
// 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;
// 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() :
arr1 = [1, 2, 3, 4, 5]
arr2 = [1, 4, 5]
#  Get the number of element in arr1
size = len(arr1)
#  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)
#  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()
arr1 = [1, 2, 3, 4, 5]
arr2 = [1, 4, 5]
#  Get the number of element in arr1
size = arr1.length
#  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
#  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;
// 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;
// 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 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;
// 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;
// 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 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();
// 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();
// 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.