Print sums of all subsets of a given set
Given an array of integers, print sums of all subsets in it. Output sums can be printed in any order.
Examples :
Input : arr[] = {2, 3} Output: 0 2 3 5 Input : arr[] = {2, 4, 5} Output : 0 2 4 5 6 7 9 11
Method 1 (Recursive)
We can recursively solve this problem. There are total 2n subsets. For every element, we consider two choices, we include it in a subset and we don’t include it in a subset. Below is recursive solution based on this idea.
C++
// C++ program to print sums of all possible // subsets. #include <bits/stdc++.h> using namespace std; // Prints sums of all subsets of arr[l..r] void subsetSums( int arr[], int l, int r, int sum = 0) { // Print current subset if (l > r) { cout << sum << " " ; return ; } // Subset including arr[l] subsetSums(arr, l + 1, r, sum + arr[l]); // Subset excluding arr[l] subsetSums(arr, l + 1, r, sum); } // Driver code int main() { int arr[] = { 5, 4, 3 }; int n = sizeof (arr) / sizeof (arr[0]); subsetSums(arr, 0, n - 1); return 0; } |
Java
// Java program to print sums // of all possible subsets. import java.io.*; class GFG { // Prints sums of all // subsets of arr[l..r] static void subsetSums( int [] arr, int l, int r, int sum) { // Print current subset if (l > r) { System.out.print(sum + " " ); return ; } // Subset including arr[l] subsetSums(arr, l + 1 , r, sum + arr[l]); // Subset excluding arr[l] subsetSums(arr, l + 1 , r, sum); } // Driver code public static void main(String[] args) { int [] arr = { 5 , 4 , 3 }; int n = arr.length; subsetSums(arr, 0 , n - 1 , 0 ); } } // This code is contributed by anuj_67 |
Python3
# Python3 program to print sums of # all possible subsets. # Prints sums of all subsets of arr[l..r] def subsetSums(arr, l, r, sum = 0 ): # Print current subset if l > r: print ( sum , end = " " ) return # Subset including arr[l] subsetSums(arr, l + 1 , r, sum + arr[l]) # Subset excluding arr[l] subsetSums(arr, l + 1 , r, sum ) # Driver code arr = [ 5 , 4 , 3 ] n = len (arr) subsetSums(arr, 0 , n - 1 ) # This code is contributed by Shreyanshi Arun. |
C#
// C# program to print sums of all possible // subsets. using System; class GFG { // Prints sums of all subsets of // arr[l..r] static void subsetSums( int [] arr, int l, int r, int sum) { // Print current subset if (l > r) { Console.Write(sum + " " ); return ; } // Subset including arr[l] subsetSums(arr, l + 1, r, sum + arr[l]); // Subset excluding arr[l] subsetSums(arr, l + 1, r, sum); } // Driver code public static void Main() { int [] arr = { 5, 4, 3 }; int n = arr.Length; subsetSums(arr, 0, n - 1, 0); } } // This code is contributed by anuj_67 |
PHP
<?php // PHP program to print sums // of all possible subsets. // Prints sums of all // subsets of arr[l..r] function subsetSums( $arr , $l , $r , $sum = 0) { // Print current subset if ( $l > $r ) { echo $sum , " " ; return ; } // Subset including arr[l] subsetSums( $arr , $l + 1, $r , $sum + $arr [ $l ]); // Subset excluding arr[l] subsetSums( $arr , $l + 1, $r , $sum ); } // Driver code $arr = array (5, 4, 3); $n = count ( $arr ); subsetSums( $arr , 0, $n - 1); // This code is contributed by anuj_67. ?> |
Javascript
<script> // Javascript program to program to print // sums of all possible subsets. // Prints sums of all // subsets of arr[l..r] function subsetSums(arr, l, r, sum) { // Print current subset if (l > r) { document.write(sum + " " ); return ; } // Subset including arr[l] subsetSums(arr, l + 1, r, sum + arr[l]); // Subset excluding arr[l] subsetSums(arr, l + 1, r, sum); } // Driver code let arr = [5, 4, 3]; let n = arr.length; subsetSums(arr, 0, n - 1, 0); // This code is contributed by code_hunt </script> |
Output :
12 9 8 5 7 4 3 0
Time complexity : O(2^n)
Auxiliary Space : O(n)
Method 2 (Iterative)
As discussed above, there are total 2n subsets. The idea is to generate a loop from 0 to 2n – 1. For every number, pick all array elements corresponding to 1s in the binary representation of the current number.
C++
// Iterative C++ program to print sums of all // possible subsets. #include <bits/stdc++.h> using namespace std; // Prints sums of all subsets of array void subsetSums( int arr[], int n) { // There are total 2^n subsets long long total = 1 << n; // Consider all numbers from 0 to 2^n - 1 for ( long long i = 0; i < total; i++) { long long sum = 0; // Consider binary representation of // current i to decide which elements // to pick. for ( int j = 0; j < n; j++) if (i & (1 << j)) sum += arr[j]; // Print sum of picked elements. cout << sum << " " ; } } // Driver code int main() { int arr[] = { 5, 4, 3 }; int n = sizeof (arr) / sizeof (arr[0]); subsetSums(arr, n); return 0; } |
Java
// Iterative Java program to print sums of all // possible subsets. import java.util.*; class GFG { // Prints sums of all subsets of array static void subsetSums( int arr[], int n) { // There are total 2^n subsets int total = 1 << n; // Consider all numbers from 0 to 2^n - 1 for ( int i = 0 ; i < total; i++) { int sum = 0 ; // Consider binary representation of // current i to decide which elements // to pick. for ( int j = 0 ; j < n; j++) if ((i & ( 1 << j)) != 0 ) sum += arr[j]; // Print sum of picked elements. System.out.print(sum + " " ); } } // Driver code public static void main(String args[]) { int arr[] = new int [] { 5 , 4 , 3 }; int n = arr.length; subsetSums(arr, n); } } // This code is contributed by spp____ |
Python3
# Iterative Python3 program to print sums of all possible subsets # Prints sums of all subsets of array def subsetSums(arr, n): # There are total 2^n subsets total = 1 << n # Consider all numbers from 0 to 2^n - 1 for i in range (total): Sum = 0 # Consider binary representation of # current i to decide which elements # to pick. for j in range (n): if ((i & ( 1 << j)) ! = 0 ): Sum + = arr[j] # Print sum of picked elements. print ( Sum , " ", end = " ") arr = [ 5 , 4 , 3 ] n = len (arr) subsetSums(arr, n); # This code is contributed by mukesh07. |
C#
// Iterative C# program to print sums of all // possible subsets. using System; class GFG { // Prints sums of all subsets of array static void subsetSums( int [] arr, int n) { // There are total 2^n subsets int total = 1 << n; // Consider all numbers from 0 to 2^n - 1 for ( int i = 0; i < total; i++) { int sum = 0; // Consider binary representation of // current i to decide which elements // to pick. for ( int j = 0; j < n; j++) if ((i & (1 << j)) != 0) sum += arr[j]; // Print sum of picked elements. Console.Write(sum + " " ); } } static void Main() { int [] arr = { 5, 4, 3 }; int n = arr.Length; subsetSums(arr, n); } } // This code is contributed by divyesh072019. |
PHP
<?php // Iterative PHP program to print // sums of all possible subsets. // Prints sums of all subsets of array function subsetSums( $arr , $n ) { // There are total 2^n subsets $total = 1 << $n ; // Consider all numbers // from 0 to 2^n - 1 for ( $i = 0; $i < $total ; $i ++) { $sum = 0; // Consider binary representation of // current i to decide which elements // to pick. for ( $j = 0; $j < $n ; $j ++) if ( $i & (1 << $j )) $sum += $arr [ $j ]; // Print sum of picked elements. echo $sum , " " ; } } // Driver code $arr = array (5, 4, 3); $n = sizeof( $arr ); subsetSums( $arr , $n ); // This Code is Contributed by ajit ?> |
Javascript
<script> // Iterative Javascript program to print sums of all // possible subsets. // Prints sums of all subsets of array function subsetSums(arr, n) { // There are total 2^n subsets let total = 1 << n; // Consider all numbers from 0 to 2^n - 1 for (let i = 0; i < total; i++) { let sum = 0; // Consider binary representation of // current i to decide which elements // to pick. for (let j = 0; j < n; j++) if ((i & (1 << j)) != 0) sum += arr[j]; // Print sum of picked elements. document.write(sum + " " ); } } let arr = [ 5, 4, 3 ]; let n = arr.length; subsetSums(arr, n); </script> |
Output :
0 5 4 9 3 8 7 12
Time Complexity: O()
Auxiliary Space: O(1)
Thanks to cfh for suggesting above iterative solution in a comment.
Note: We haven’t actually created sub-sets to find their sums rather we have just used recursion to find sum of non-contiguous sub-sets of the given set.
A more Efficient Iterative method:
In this method, while visiting a new element, we take its sum with all previously stored sums. This method stores the sums of all subsets and hence it is valid for smaller inputs.
C++
// Iterative C++ program to print sums of all // possible subsets. #include <bits/stdc++.h> using namespace std; // Prints sums of all subsets of array void subsetSums( int nums[], int n) { // There are total 2^n subsets vector< int > s = {0}; //store the sums for ( int i = 0; i <n; i++) { const int v = s.size(); for ( int t = 0; t < v; t++) { s.push_back(s[t] + nums[i]); //add this element with previous subsets } } // Print for ( int i=0;i<s.size();i++) cout << s[i] << " " ; } // Driver code int main() { int arr[] = { 5, 4, 3 }; int n = sizeof (arr) / sizeof (arr[0]); subsetSums(arr, n); return 0; } |
Java
import java.util.ArrayList; public class Main { public static void subsetSums( int [] nums, int n) { ArrayList<Integer> s = new ArrayList<Integer>(); s.add( 0 ); for ( int i = 0 ; i < n; i++) { int v = s.size(); for ( int t = 0 ; t < v; t++) { s.add(s.get(t) + nums[i]); } } for ( int i = 0 ; i < s.size(); i++) { System.out.print(s.get(i) + " " ); } } public static void main(String[] args) { int [] arr = { 5 , 4 , 3 }; int n = arr.length; subsetSums(arr, n); } } |
Python3
# Iterative Python program to print sums of all # possible subsets. # Prints sums of all subsets of array def subsetSums(nums,n): # There are total 2^n subsets s = [ 0 ] for i in range (n): v = len (s) for t in range (v): s.append(s[t] + nums[i]) # add this element with previous subsets # Print print (s,end = ' ' ) # Driver code arr = [ 5 , 4 , 3 ] n = len (arr) subsetSums(arr, n) |
C#
// C# program to print sums of all possible subsets using System; public class Subsets { static void subsetSums( int [] nums, int n) { // There are total 2^n subsets int [] s = new int [1]; s[0] = 0; for ( int i = 0; i < n; i++) { int v = s.Length; for ( int t = 0; t < v; t++) { // add the current element with all previous subsets Array.Resize( ref s, s.Length + 1); // increase the size of the array s[s.Length - 1] = s[t] + nums[i]; // add the current element with previous subsets } } // Print Console.Write( string .Join( " " , s)); } public static void Main() { int [] arr = { 5, 4, 3 }; int n = arr.Length; subsetSums(arr, n); } } |
Javascript
// Iterative JavaScript program to print sums of all possible subsets function subsetSums(nums, n) { // There are total 2^n subsets let s = [0]; for (let i = 0; i < n; i++) { let v = s.length; for (let t = 0; t < v; t++) { s.push(s[t] + nums[i]); // add this element with previous subsets } } // Print for (let i=0; i<s.length; i++) { process.stdout.write(s[i]+ " " ); } } // Driver code let arr = [5, 4, 3]; let n = arr.length; subsetSums(arr, n); |
Output:
0 5 4 9 3 8 7 12
Time Complexity: O(2^N)
Auxiliary Space: O(N) for storing the ans
Thanks to shivampatidar6116 for suggesting the above iterative solution
The above-mentioned techniques can be used to perform various operations on sub-sets like multiplication, division, XOR, OR, etc, without actually creating and storing the sub-sets and thus making the program memory efficient.