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.
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 : 90Resultant 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.
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