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(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)
C++
// 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; } |
Java
// Java program to find sum of all subsets // of a set. class GFG { static long findSumSubsets( int n) { // sum of subsets is (n * (n + 1) / 2) * // pow(2, n-1) return (n * (n + 1 ) / 2 ) * ( 1 << (n - 1 )); } // Driver code public static void main(String[] args) { int n = 3 ; System.out.print(findSumSubsets(n)); } } // This code is contributed by Anant Agarwal. |
Python3
# Python program to find # sum of all subsets # of a set. def findSumSubsets( n): # sum of subsets # is (n * (n + 1) / 2) * # pow(2, n-1) return (n * (n + 1 ) / 2 ) * ( 1 << (n - 1 )) # Driver code n = 3 print (findSumSubsets(n)) # This code is contributed # by sunnysingh. |
C#
// C# program to find sum of all subsets // of a set. using System; class GFG { static long findSumSubsets( int n) { // sum of subsets is (n * (n + 1) / 2) * // pow(2, n-1) return (n * (n + 1) / 2) * (1 << (n - 1)); } // Driver code public static void Main() { int n = 3; Console.WriteLine(findSumSubsets(n)); } } // This code is contributed by vt_m. |
PHP
<?php // PHP program to find sum // of all subsets of a set function findSumSubsets( $n ) { // sum of subsets is (n * // (n + 1) / 2) * pow(2, n-1) return ( $n * ( $n + 1) / 2) * (1 << ( $n - 1)); } // Driver Code $n = 3; echo findSumSubsets( $n ); // This code is contributed by ajit ?> |
Javascript
<script> // javascript program to find sum of all subsets // of a set. function findSumSubsets( n) { // sum of subsets is (n * (n + 1) / 2) * // pow(2, n-1) return (n * (n + 1) / 2) * (1 << (n - 1)); } // Driven Program let n = 3; document.write(findSumSubsets(n)); // This code contributed by aashish1995 </script> |
Output :
24
Time Complexity: O(1)
Auxiliary Space: O(1)
Contact Us