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)
A 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^{(n1)} times. So our required sum is (1 + 2 + 3 + ..+ n) * 2^{(n1)}. The sum can be written as (n * (n + 1)/2) * 2^{(n1)}

// 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, n1)
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 growthoriented 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