Sum of all subsets of a set formed by first n natural numbers

Given a number n, we need to find the sum of all the elements from all possible subsets of a set formed by first n natural numbers.

Examples:

Input :  n = 2
Output : 6
Possible subsets are {{1}, {2}, 
{1, 2}}. Sum of elements in subsets
is 1 + 2 + 1 + 2 = 6

Input :  n = 3
Output : 24
Possible subsets are {{1}, {2}, {3}, 
{1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}
Sum of subsets is : 
1 + 2 + 3 + (1 + 2) + (1 + 3) + 
(2 + 3) + (1 + 2 + 3)

simple solution is to generate all subsets. For every subset, compute its sum and finally return overall sum.

An efficient solution is based on the fact that every number from 1 to n appears exactly 2(n-1) times. So our required sum is (1 + 2 + 3 + ..+ n) * 2(n-1). The sum can be written as (n * (n + 1)/2) * 2(n-1)

// CPP program to find sum of all subsets
// of a set.
#include <bits/stdc++.h>
using namespace std;
unsigned long long findSumSubsets(int n)
{
    // sum of subsets is (n * (n + 1) / 2) *
    // pow(2, n-1)
    return (n * (n + 1) / 2) * (1 << (n - 1));
}
int main()
{
    int n = 3;
    cout << findSumSubsets(n);
    return 0;
}

Output:

24

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide


rakesh

Leave a Reply

Your email address will not be published. Required fields are marked *

Skip to toolbar