Skip to main content

Print sums of all subsets of a given set

Print sum of all subsets of a given array refers to the sum of all possible combinations of elements in the array, including subsets with no elements, one element, two elements, and so on. For example, if the given array is [1, 2, 3], the sum of all subsets would be 0, 1 , 2 , 3 , (1 + 2) , (1 + 3) , (2 + 3) , (1 + 2 + 3).

Note result order is not important.

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
Last updated on by Kalkicode




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