Given an array a of size N. The task is to find the sum of the sums of all possible subsets.
Examples:
Input: a[] = {3, 7}
Output: 20
The subsets are: {3} {7} {3, 7}
{3, 7} = 10
{3} = 3
{7} = 7
10 + 3 + 7 = 20
Input: a[] = {10, 16, 14, 9}
Output: 392
Naive Approach: A naive approach is to find all the subsets using power set and then summate all the possible subsets to get the answer.
C++
#include <bits/stdc++.h>
using namespace std;
int helper( int N, int nums[], int sum, int idx)
{
if (idx == N) {
return sum;
}
int picked = helper(N, nums, sum + nums[idx], idx + 1);
int notPicked = helper(N, nums, sum, idx + 1);
return picked + notPicked;
}
int sumOfSubset( int arr[], int n)
{
return helper(n, arr, 0, 0);
}
int main()
{
int arr[] = { 3, 7 };
int n = sizeof (arr) / sizeof (arr[0]);
cout << sumOfSubset(arr, n);
return 0;
}
|
Java
import java.io.*;
class GFG {
static int helper( int N, int nums[], int sum, int idx)
{
if (idx == N) {
return sum;
}
int picked
= helper(N, nums, sum + nums[idx], idx + 1 );
int notPicked = helper(N, nums, sum, idx + 1 );
return picked + notPicked;
}
static int sumOfSubset( int arr[], int n)
{
return helper(n, arr, 0 , 0 );
}
public static void main(String[] args)
{
int arr[] = { 3 , 7 };
int n = arr.length;
System.out.println(sumOfSubset(arr, n));
}
}
|
Python3
def helper(N, nums, sum , idx):
if idx = = N:
return sum
picked = helper(N, nums, sum + nums[idx], idx + 1 )
not_picked = helper(N, nums, sum , idx + 1 )
return picked + not_picked
def sum_of_subset(arr, n):
return helper(n, arr, 0 , 0 )
arr = [ 3 , 7 ]
n = len (arr)
print (sum_of_subset(arr, n))
|
C#
using System;
class GFG {
static int helper( int N, int [] nums, int sum, int idx)
{
if (idx == N) {
return sum;
}
int picked
= helper(N, nums, sum + nums[idx], idx + 1);
int notPicked = helper(N, nums, sum, idx + 1);
return picked + notPicked;
}
static int sumOfSubset( int [] arr, int n)
{
return helper(n, arr, 0, 0);
}
public static void Main()
{
int [] arr = { 3, 7 };
int n = arr.Length;
Console.WriteLine(sumOfSubset(arr, n));
}
}
|
Javascript
function helper(N, nums, sum, idx)
{
if (idx == N)
{
return sum;
}
let picked = helper(N, nums, sum + nums[idx], idx + 1);
let notPicked = helper(N, nums, sum, idx + 1);
return picked + notPicked;
}
function sumOfSubset(arr, n)
{
return helper(n, arr, 0, 0);
}
let arr = [ 3, 7 ];
let n = arr.length;
console.log(sumOfSubset(arr, n));
|
Space Complexity: O(N) because of Recursion Stack Space
Efficient Approach: An efficient approach is to solve the problem using observation. If we write all the subsequences, a common point of observation is that each number appears 2(N – 1) times in a subset and hence will lead to the 2(N-1) as the contribution to the sum. Iterate through the array and add (arr[i] * 2N-1) to the answer.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
int sumOfSubset( int a[], int n)
{
int times = pow (2, n - 1);
int sum = 0;
for ( int i = 0; i < n; i++) {
sum = sum + (a[i] * times);
}
return sum;
}
int main()
{
int a[] = { 3, 7 };
int n = sizeof (a) / sizeof (a[0]);
cout << sumOfSubset(a, n);
}
|
Java
class GFG
{
static int sumOfSubset( int []a, int n)
{
int times = ( int )Math.pow( 2 , n - 1 );
int sum = 0 ;
for ( int i = 0 ; i < n; i++)
{
sum = sum + (a[i] * times);
}
return sum;
}
public static void main(String[] args)
{
int []a = { 3 , 7 };
int n = a.length;
System.out.println(sumOfSubset(a, n));
}
}
|
Python3
def SumOfSubset(a, n):
times = pow ( 2 , n - 1 )
Sum = 0
for i in range (n):
Sum = Sum + (a[i] * times)
return Sum
a = [ 3 , 7 ]
n = len (a)
print (SumOfSubset(a, n))
|
C#
using System;
class GFG
{
static int sumOfSubset( int []a, int n)
{
int times = ( int )Math.Pow(2, n - 1);
int sum = 0;
for ( int i = 0; i < n; i++)
{
sum = sum + (a[i] * times);
}
return sum;
}
public static void Main()
{
int []a = { 3, 7 };
int n = a.Length;
Console.Write(sumOfSubset(a, n));
}
}
|
Javascript
<script>
function sumOfSubset(a , n) {
var times = parseInt( Math.pow(2, n - 1));
var sum = 0;
for (i = 0; i < n; i++) {
sum = sum + (a[i] * times);
}
return sum;
}
var a = [ 3, 7 ];
var n = a.length;
document.write(sumOfSubset(a, n));
</script>
|
Time Complexity: O(N)
Space Complexity: O(1)
Note: If N is large, the answer can overflow, thereby use larger data-type.