Posted on by Kalkicode
Code Greedy

# Print sums of all subsets of a given set

The Subset Sum Problem is a classic computational problem in computer science and mathematics. Given a set of integers, the task is to find all possible sums that can be formed using subsets of these integers. In other words, for each possible subset of the given set, the sum of its elements needs to be computed and printed.

## Problem Statement and Example

Consider the set {1, 2, 3, 4, 5}. The goal is to find all the possible sums that can be formed using its subsets. For this set, the sums include 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, and so on. Similarly, for the set {1, 4, 3}, the possible subset sums are 0, 1, 3, 4, 5, 7, and 8.

## Idea to Solve the Problem

The problem can be solved using recursion, where at each step, we have two choices: either include the current element in the subset sum or exclude it. We can recursively explore both these choices for each element in the set until we have considered all elements. The base case for the recursion is when we have considered all elements (reached the end of the array).

## Pseudocode

``````function subsetSum(arr, size, i, sum):
if i == size:
print sum
return
subsetSum(arr, size, i + 1, sum)       // Exclude current element
subsetSum(arr, size, i + 1, sum + arr[i])  // Include current element

# Main
arr1 = [1, 2, 3, 4, 5]
size = length(arr1)
print "All Subset Sum:"
subsetSum(arr1, size, 0, 0)

arr2 = [1, 4, 3]
size = length(arr2)
print "All Subset Sum:"
subsetSum(arr2, size, 0, 0)``````

## Algorithm Explanation

1. Start by defining the subsetSum function that takes the array, its size, the current index (i), and the current sum as arguments.
2. In the function, check if the current index (i) has reached the size of the array. If so, print the current sum and return.
3. Otherwise, make two recursive calls: a. One call excludes the current element from the sum and moves to the next index (i + 1). b. The other call includes the current element in the sum and moves to the next index (i + 1).
4. The recursion will explore all possible combinations of including and excluding elements from the subset and generate all possible subset sums.

## Code Solution

``````/*
C Program
Print sums of all subsets of a given set
*/
#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");
}
// Find the subset sum in given array
void subsetSum(int arr[], int size, int i, int sum)
{
if (i == size)
{
printf(" %d", sum);
return;
}
// Recursively, find subset sum
subsetSum(arr, size, i + 1, sum);
subsetSum(arr, size, i + 1, sum + arr[i]);
}
int main(int argc, char
const *argv[])
{
int arr1[] = {
1 , 2 , 3 , 4 , 5
};
int arr2[] = {
1 , 4 , 3
};
// Get the number of element in array
int size = sizeof(arr1) / sizeof(arr1[0]);
printData(arr1, size);
printf(" All Subset Sum : \n");
// Find sum of existing subset
subsetSum(arr1, size, 0, 0);
size = sizeof(arr2) / sizeof(arr2[0]);
printData(arr2, size);
printf(" All Subset Sum : \n");
// Find sum of existing subset
subsetSum(arr2, size, 0, 0);
return 0;
}``````

#### Output

`````` Array elements
1 2 3 4 5
All Subset Sum :
0 5 4 9 3 8 7 12 2 7 6 11 5 10 9 14 1 6 5 10 4 9 8 13 3 8 7 12 6 11 10 15
Array elements
1 4 3
All Subset Sum :
0 3 4 7 1 4 5 8``````
``````/*
Java program
Print sums of all subsets of a given set
*/
class Subsets
{
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");
}
// Find the subset sum in given array
public void subsetSum(int[] arr, int size, int i, int sum)
{
if (i == size)
{
System.out.print(" " + sum);
return;
}
// Recursively, find subset sum
subsetSum(arr, size, i + 1, sum);
subsetSum(arr, size, i + 1, sum + arr[i]);
}
public static void main(String[] args)
{
int[] arr1 = {
1 , 2 , 3 , 4 , 5
};
int[] arr2 = {
1 , 4 , 3
};
// Get the number of element in array
int size = arr1.length;
System.out.print(" All Subset Sum : \n");
// Find sum of existing subset
size = arr2.length;;
System.out.print(" All Subset Sum : \n");
// Find sum of existing subset
}
}``````

#### Output

`````` Array elements
1 2 3 4 5
All Subset Sum :
0 5 4 9 3 8 7 12 2 7 6 11 5 10 9 14 1 6 5 10 4 9 8 13 3 8 7 12 6 11 10 15
Array elements
1 4 3
All Subset Sum :
0 3 4 7 1 4 5 8``````
``````// Include header file
#include <iostream>
using namespace std;

/*
C++ program
Print sums of all subsets of a given set
*/

class Subsets
{
public:
void printData(int arr[], int size)
{
cout << "\n Array elements \n";
for (int i = 0; i < size; ++i)
{
cout << " " << arr[i];
}
cout << "\n";
}
// Find the subset sum in given array
void subsetSum(int arr[], int size, int i, int sum)
{
if (i == size)
{
cout << " " << sum;
return;
}
// Recursively, find subset sum
this->subsetSum(arr, size, i + 1, sum);
this->subsetSum(arr, size, i + 1, sum + arr[i]);
}
};
int main()
{
int arr1[] = {
1 , 2 , 3 , 4 , 5
};
int arr2[] = {
1 , 4 , 3
};
// Get the number of element in array
int size = sizeof(arr1) / sizeof(arr1[0]);
cout << " All Subset Sum : \n";
// Find sum of existing subset
size = sizeof(arr2) / sizeof(arr2[0]);;
cout << " All Subset Sum : \n";
// Find sum of existing subset
return 0;
}``````

#### Output

`````` Array elements
1 2 3 4 5
All Subset Sum :
0 5 4 9 3 8 7 12 2 7 6 11 5 10 9 14 1 6 5 10 4 9 8 13 3 8 7 12 6 11 10 15
Array elements
1 4 3
All Subset Sum :
0 3 4 7 1 4 5 8``````
``````// Include namespace system
using System;
/*
C# program
Print sums of all subsets of a given set
*/
public class Subsets
{
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");
}
// Find the subset sum in given array
public void subsetSum(int[] arr, int size, int i, int sum)
{
if (i == size)
{
Console.Write(" " + sum);
return;
}
// Recursively, find subset sum
subsetSum(arr, size, i + 1, sum);
subsetSum(arr, size, i + 1, sum + arr[i]);
}
public static void Main(String[] args)
{
int[] arr1 = {
1 , 2 , 3 , 4 , 5
};
int[] arr2 = {
1 , 4 , 3
};
// Get the number of element in array
int size = arr1.Length;
Console.Write(" All Subset Sum : \n");
// Find sum of existing subset
size = arr2.Length;;
Console.Write(" All Subset Sum : \n");
// Find sum of existing subset
}
}``````

#### Output

`````` Array elements
1 2 3 4 5
All Subset Sum :
0 5 4 9 3 8 7 12 2 7 6 11 5 10 9 14 1 6 5 10 4 9 8 13 3 8 7 12 6 11 10 15
Array elements
1 4 3
All Subset Sum :
0 3 4 7 1 4 5 8``````
``````<?php
/*
Php program
Print sums of all subsets of a given set
*/
class Subsets
{
public	function printData( & \$arr, \$size)
{
echo "\n Array elements \n";
for (\$i = 0; \$i < \$size; ++\$i)
{
echo " ". \$arr[\$i];
}
echo "\n";
}
// Find the subset sum in given array
public	function subsetSum( & \$arr, \$size, \$i, \$sum)
{
if (\$i == \$size)
{
echo " ". \$sum;
return;
}
// Recursively, find subset sum
\$this->subsetSum(\$arr, \$size, \$i + 1, \$sum);
\$this->subsetSum(\$arr, \$size, \$i + 1, \$sum + \$arr[\$i]);
}
}

function main()
{
\$arr1 = array(1, 2, 3, 4, 5);
\$arr2 = array(1, 4, 3);
// Get the number of element in array
\$size = count(\$arr1);
echo " All Subset Sum : \n";
// Find sum of existing subset
\$size = count(\$arr2);;
echo " All Subset Sum : \n";
// Find sum of existing subset
}
main();``````

#### Output

`````` Array elements
1 2 3 4 5
All Subset Sum :
0 5 4 9 3 8 7 12 2 7 6 11 5 10 9 14 1 6 5 10 4 9 8 13 3 8 7 12 6 11 10 15
Array elements
1 4 3
All Subset Sum :
0 3 4 7 1 4 5 8``````
``````/*
Node Js program
Print sums of all subsets of a given set
*/
class Subsets
{
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");
}
// Find the subset sum in given array
subsetSum(arr, size, i, sum)
{
if (i == size)
{
process.stdout.write(" " + sum);
return;
}
// Recursively, find subset sum
this.subsetSum(arr, size, i + 1, sum);
this.subsetSum(arr, size, i + 1, sum + arr[i]);
}
}

function main()
{
var arr1 = [1, 2, 3, 4, 5];
var arr2 = [1, 4, 3];
// Get the number of element in array
var size = arr1.length;
process.stdout.write(" All Subset Sum : \n");
// Find sum of existing subset
size = arr2.length;;
process.stdout.write(" All Subset Sum : \n");
// Find sum of existing subset
}
main();``````

#### Output

`````` Array elements
1 2 3 4 5
All Subset Sum :
0 5 4 9 3 8 7 12 2 7 6 11 5 10 9 14 1 6 5 10 4 9 8 13 3 8 7 12 6 11 10 15
Array elements
1 4 3
All Subset Sum :
0 3 4 7 1 4 5 8``````
``````#   Python 3 program
#   Print sums of all subsets of a given set

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

print(end = "\n")

#  Find the subset sum in given array
def subsetSum(self, arr, size, i, sum) :
if (i == size) :
print(" ", sum, end = "")
return

#  Recursively, find subset sum
self.subsetSum(arr, size, i + 1, sum)
self.subsetSum(arr, size, i + 1, sum + arr[i])

def main() :
arr1 = [1, 2, 3, 4, 5]
arr2 = [1, 4, 3]
#  Get the number of element in array
size = len(arr1)
print(" All Subset Sum : ")
#  Find sum of existing subset
size = len(arr2)
print(" All Subset Sum : ")
#  Find sum of existing subset

if __name__ == "__main__": main()``````

#### Output

`````` Array elements
1  2  3  4  5
All Subset Sum :
0  5  4  9  3  8  7  12  2  7  6  11  5  10  9  14  1  6  5  10  4  9  8  13  3  8  7  12  6  11  10  15
Array elements
1  4  3
All Subset Sum :
0  3  4  7  1  4  5  8``````
``````#   Ruby program
#   Print sums of all subsets of a given set

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

print("\n")
end

#  Find the subset sum in given array
def subsetSum(arr, size, i, sum)
if (i == size)
print(" ", sum)
return
end

#  Recursively, find subset sum
self.subsetSum(arr, size, i + 1, sum)
self.subsetSum(arr, size, i + 1, sum + arr[i])
end

end

def main()
arr1 = [1, 2, 3, 4, 5]
arr2 = [1, 4, 3]
#  Get the number of element in array
size = arr1.length
print(" All Subset Sum : \n")
#  Find sum of existing subset
size = arr2.length
print(" All Subset Sum : \n")
#  Find sum of existing subset
end

main()``````

#### Output

`````` Array elements
1 2 3 4 5
All Subset Sum :
0 5 4 9 3 8 7 12 2 7 6 11 5 10 9 14 1 6 5 10 4 9 8 13 3 8 7 12 6 11 10 15
Array elements
1 4 3
All Subset Sum :
0 3 4 7 1 4 5 8``````
``````/*
Scala program
Print sums of all subsets of a given set
*/
class Subsets
{
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");
}
// Find the subset sum in given array
def subsetSum(arr: Array[Int], size: Int, i: Int, sum: Int): Unit = {
if (i == size)
{
print(" " + sum);
return;
}
// Recursively, find subset sum
this.subsetSum(arr, size, i + 1, sum);
this.subsetSum(arr, size, i + 1, sum + arr(i));
}
}
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, 3);
// Get the number of element in array
var size: Int = arr1.length;
print(" All Subset Sum : \n");
// Find sum of existing subset
size = arr2.length;;
print(" All Subset Sum : \n");
// Find sum of existing subset
}
}``````

#### Output

`````` Array elements
1 2 3 4 5
All Subset Sum :
0 5 4 9 3 8 7 12 2 7 6 11 5 10 9 14 1 6 5 10 4 9 8 13 3 8 7 12 6 11 10 15
Array elements
1 4 3
All Subset Sum :
0 3 4 7 1 4 5 8``````
``````/*
Swift 4 program
Print sums of all subsets of a given set
*/
class Subsets
{
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");
}
// Find the subset sum in given array
func subsetSum(_ arr: [Int], _ size: Int, _ i: Int, _ sum: Int)
{
if (i == size)
{
print(" ", sum, terminator: "");
return;
}
// Recursively, find subset sum
self.subsetSum(arr, size, i + 1, sum);
self.subsetSum(arr, size, i + 1, sum + arr[i]);
}
}
func main()
{
let arr1: [Int] = [1, 2, 3, 4, 5];
let arr2: [Int] = [1, 4, 3];
// Get the number of element in array
var size: Int = arr1.count;
print(" All Subset Sum : ");
// Find sum of existing subset
size = arr2.count;
print(" All Subset Sum : ");
// Find sum of existing subset
}
main();``````

#### Output

`````` Array elements
1  2  3  4  5
All Subset Sum :
0  5  4  9  3  8  7  12  2  7  6  11  5  10  9  14  1  6  5  10  4  9  8  13  3  8  7  12  6  11  10  15
Array elements
1  4  3
All Subset Sum :
0  3  4  7  1  4  5  8``````
``````/*
Kotlin program
Print sums of all subsets of a given set
*/
class Subsets
{
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");
}
// Find the subset sum in given array
fun subsetSum(arr: Array <Int> , size: Int, i: Int, sum: Int): Unit
{
if (i == size)
{
print(" " + sum);
return;
}
// Recursively, find subset sum
this.subsetSum(arr, size, i + 1, sum);
this.subsetSum(arr, size, i + 1, sum + arr[i]);
}
}
fun main(args: Array <String> ): Unit
{
var arr1: Array < Int > = arrayOf(1, 2, 3, 4, 5);
var arr2: Array < Int > = arrayOf(1, 4, 3);
// Get the number of element in array
var size: Int = arr1.count();
print(" All Subset Sum : \n");
// Find sum of existing subset
size = arr2.count();
print(" All Subset Sum : \n");
// Find sum of existing subset
}``````

#### Output

`````` Array elements
1 2 3 4 5
All Subset Sum :
0 5 4 9 3 8 7 12 2 7 6 11 5 10 9 14 1 6 5 10 4 9 8 13 3 8 7 12 6 11 10 15
Array elements
1 4 3
All Subset Sum :
0 3 4 7 1 4 5 8``````

## Resultant Output Explanation

For the given sets {1, 2, 3, 4, 5} and {1, 4, 3}, the code generates all possible subset sums as shown in the output.

## Time Complexity

The time complexity of this algorithm depends on the number of subsets that can be formed from the given set. Since there are 2^n subsets for a set of n elements, the algorithm's time complexity is exponential, O(2^n), where n is the number of elements in the set. This is because the algorithm considers all possible subsets and generates their sums. The exponential nature of this problem limits its efficiency for larger sets.

## 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.

Categories
Relative Post