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 codeint 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 codearr = [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 codelet 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 arrayvoid 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 codeint 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 arraydef 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 arrayvoid 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 codeint 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 arraydef 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 codearr = [5, 4, 3 ]n = len(arr)subsetSums(arr, n) |
C#
// C# program to print sums of all possible subsetsusing 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 subsetsfunction 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 codelet 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.
This article is contributed by Aditya Gupta. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
