Given a list arr of N integers, print sums of all subsets in it in C++

Sums of all Subsets in C++

Here, in this page we will discuss the program for printing the sums of all subsets in C++ programming language. We are given with a list array of N integers, and need to print the all subsets sums.

Sums of all Subsets in C++

Method Discussed :

  • Method 1 : Iterative Method
  • Method 2 : Recursive Method

Let’s discuss the algorithm for both the methods in brief.

 

Method 1 :

  • The total number of subset will be 2n, where n is the size of the array.
  • Run a loop from  0 to 2n -1.
  • Now, Pick all array elements which correspond to 1s in binary representation of ith number.

Method 1 : Code in C++

Run
#include <bits/stdc++.h>
using namespace std;
 
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;
        for (int j = 0; j < n; j++)
            if (i & (1 << j))
                sum += arr[j];
 
        // Print sum of picked elements.
        cout << sum << " ";
    }
}
 
int main()
{
    int arr[] = { 4, 3, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    subsetSums(arr, n);
    return 0;
}

Output

0 4 3 7 5 9 8 12

Method 2 :

In this method we will discuss the recursive way to find the subsets sum, in this either we will take the elements value in the sum or not. Based on this approach we will find the subsets sum.

Method 2 : Code in C++

Run
#include <bits/stdc++.h>
using namespace std;
 
void subsetSum(int arr[], int l, int r, int sum = 0)
{
    if (l > r) {
        cout << sum << " ";
        return;
    }
 
    subsetSum(arr, l + 1, r, sum + arr[l]);
 
    subsetSum(arr, l + 1, r, sum);
}
 
int main()
{
    int arr[] = { 4, 3, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    subsetSum(arr, 0, n - 1);
    return 0;
}

Output

12 7 9 4 8 3 5 0

One comment on “Given a list arr of N integers, print sums of all subsets in it in C++”


  • amanbajpai5734

    #include
    using namespace std;

    int findSum(string num)
    {
    int sum=0;
    for(int i=0;i<num.length();i++){
    sum= sum+num[i]-48;
    }
    return sum;
    }

    void powerSet(string str, int i, string curr)
    {
    int n=str.length();
    if(i==n)
    {
    int x = findSum(curr);
    cout<<x<<endl;
    return;
    }
    powerSet(str,i+1,curr+str[i]);
    powerSet(str,i+1,curr);
    }

    int main()
    {
    string str;
    string arr[]= {"4", "3", "5"};
    int n = sizeof(arr)/sizeof(arr[0]);
    for(int i=0;i<n;i++)
    str=str+arr[i];

    powerSet(str,0,"");
    return 0;
    }