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

October 14, 2022

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++
While loop 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

Program for octal to decimal conversion

Program for hexadecimal to decimal conversion

Program for decimal to binary conversion

Program for decimal to octal conversion

Program for decimal to hexadecimal conversion

 

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get Prime
While loop in C

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


  • Yash

    def sub(aray,output,index,ans):
    if index>=len(aray):
    a=sum((output[:]))
    ans.append(a)
    print(ans)
    return
    else:
    #exclude
    sub(aray,output,index+1,ans)

    #include
    element=aray[index]
    output.append(element)
    sub(aray,output,index+1,ans)
    output.pop()

    aray=[1,2,3]
    output=[]
    ans=[]
    index=0
    print(sub(aray,output,index,ans))

    0

  • 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;
    }

    1