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)
	{
		Subsets task = new Subsets();
		int[] arr1 = {
			1 , 2 , 3 , 4 , 5
		};
		int[] arr2 = {
			1 , 4 , 3
		};
		// Get the number of element in array
		int size = arr1.length;
		task.printData(arr1, size);
		System.out.print(" All Subset Sum : \n");
		// Find sum of existing subset
		task.subsetSum(arr1, size, 0, 0);
		size = arr2.length;;
		task.printData(arr2, size);
		System.out.print(" All Subset Sum : \n");
		// Find sum of existing subset
		task.subsetSum(arr2, size, 0, 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 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()
{
	Subsets task = Subsets();
	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]);
	task.printData(arr1, size);
	cout << " All Subset Sum : \n";
	// Find sum of existing subset
	task.subsetSum(arr1, size, 0, 0);
	size = sizeof(arr2) / sizeof(arr2[0]);;
	task.printData(arr2, size);
	cout << " All Subset Sum : \n";
	// Find sum of existing subset
	task.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
// 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)
	{
		Subsets task = new Subsets();
		int[] arr1 = {
			1 , 2 , 3 , 4 , 5
		};
		int[] arr2 = {
			1 , 4 , 3
		};
		// Get the number of element in array
		int size = arr1.Length;
		task.printData(arr1, size);
		Console.Write(" All Subset Sum : \n");
		// Find sum of existing subset
		task.subsetSum(arr1, size, 0, 0);
		size = arr2.Length;;
		task.printData(arr2, size);
		Console.Write(" All Subset Sum : \n");
		// Find sum of existing subset
		task.subsetSum(arr2, size, 0, 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
<?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()
{
	$task = new Subsets();
	$arr1 = array(1, 2, 3, 4, 5);
	$arr2 = array(1, 4, 3);
	// Get the number of element in array
	$size = count($arr1);
	$task->printData($arr1, $size);
	echo " All Subset Sum : \n";
	// Find sum of existing subset
	$task->subsetSum($arr1, $size, 0, 0);
	$size = count($arr2);;
	$task->printData($arr2, $size);
	echo " All Subset Sum : \n";
	// Find sum of existing subset
	$task->subsetSum($arr2, $size, 0, 0);
}
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 task = new Subsets();
	var arr1 = [1, 2, 3, 4, 5];
	var arr2 = [1, 4, 3];
	// Get the number of element in array
	var size = arr1.length;
	task.printData(arr1, size);
	process.stdout.write(" All Subset Sum : \n");
	// Find sum of existing subset
	task.subsetSum(arr1, size, 0, 0);
	size = arr2.length;;
	task.printData(arr2, size);
	process.stdout.write(" All Subset Sum : \n");
	// Find sum of existing subset
	task.subsetSum(arr2, size, 0, 0);
}
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() :
	task = Subsets()
	arr1 = [1, 2, 3, 4, 5]
	arr2 = [1, 4, 3]
	#  Get the number of element in array
	size = len(arr1)
	task.printData(arr1, size)
	print(" All Subset Sum : ")
	#  Find sum of existing subset
	task.subsetSum(arr1, size, 0, 0)
	size = len(arr2)
	task.printData(arr2, size)
	print(" All Subset Sum : ")
	#  Find sum of existing subset
	task.subsetSum(arr2, size, 0, 0)

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() 
	task = Subsets.new()
	arr1 = [1, 2, 3, 4, 5]
	arr2 = [1, 4, 3]
	#  Get the number of element in array
	size = arr1.length
	task.printData(arr1, size)
	print(" All Subset Sum : \n")
	#  Find sum of existing subset
	task.subsetSum(arr1, size, 0, 0)
	size = arr2.length
	task.printData(arr2, size)
	print(" All Subset Sum : \n")
	#  Find sum of existing subset
	task.subsetSum(arr2, size, 0, 0)
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;
		task.printData(arr1, size);
		print(" All Subset Sum : \n");
		// Find sum of existing subset
		task.subsetSum(arr1, size, 0, 0);
		size = arr2.length;;
		task.printData(arr2, size);
		print(" All Subset Sum : \n");
		// Find sum of existing subset
		task.subsetSum(arr2, size, 0, 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
/*
  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 task: Subsets = Subsets();
	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;
	task.printData(arr1, size);
	print(" All Subset Sum : ");
	// Find sum of existing subset
	task.subsetSum(arr1, size, 0, 0);
	size = arr2.count;
	task.printData(arr2, size);
	print(" All Subset Sum : ");
	// Find sum of existing subset
	task.subsetSum(arr2, size, 0, 0);
}
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 task: Subsets = Subsets();
	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();
	task.printData(arr1, size);
	print(" All Subset Sum : \n");
	// Find sum of existing subset
	task.subsetSum(arr1, size, 0, 0);
	size = arr2.count();
	task.printData(arr2, size);
	print(" All Subset Sum : \n");
	// Find sum of existing subset
	task.subsetSum(arr2, size, 0, 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

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.

New Comment