Suma de las sumas de todos los subconjuntos posibles

Dada una array a de tamaño N . La tarea es encontrar la suma de las sumas de todos los subconjuntos posibles. 
Ejemplos: 
 

Entrada: a[] = {3, 7} 
Salida: 20 
Los subconjuntos son: {3} {7} {3, 7} 
{3, 7} = 10 
{3} = 3 
{7} = 7 
10 + 3 + 7 = 20 
Entrada: a[] = {10, 16, 14, 9} 
Salida: 392 
 

Enfoque ingenuo : un enfoque ingenuo es encontrar todos los subconjuntos usando el conjunto potencia y luego sumar todos los subconjuntos posibles para obtener la respuesta. 

// C++ program to check if there is a subset
// with sum divisible by m.
#include <bits/stdc++.h>
using namespace std;
 
int helper(int N, int nums[], int sum, int idx)
{
    // if we reach last index
    if (idx == N) {
        // and if the sum mod m is zero
        return sum;
    }
 
    // 2 choices - to pick or to not pick
    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);
}
 
// Driver code
int main()
{
    int arr[] = { 3, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << sumOfSubset(arr, n);
 
    return 0;
}

20

Complejidad de tiempo : O (2 ^N )

Complejidad del espacio: O(N) debido a la pila de recursividad
Enfoque eficiente del espacio : un enfoque eficiente es resolver el problema mediante la observación. Si escribimos todas las subsecuencias, un punto común de observación es que cada número aparece 2 ^{(N – 1)} veces en un subconjunto y por lo tanto conducirá al 2 ^(N-1) como contribución a la suma. Repita la array y agregue (arr[i] * 2 ^N-1 ) a la respuesta. 
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ program to find the sum of
// the addition of all possible subsets.
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the sum
// of sum of all the subset
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;
}
 
// Driver Code
int main()
{
    int a[] = { 3, 7 };
    int n = sizeof(a) / sizeof(a[0]);
    cout << sumOfSubset(a, n);
}

// Java program to find the sum of
// the addition of all possible subsets.
class GFG
{
     
// Function to find the sum
// of sum of all the subset
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;
}
 
// Driver Code
public static void main(String[] args)
{
    int []a = { 3, 7 };
    int n = a.length;
    System.out.println(sumOfSubset(a, n));
}
}
 
// This code is contributed by 29AjayKumar

# Python3 program to find the Sum of
# the addition of all possible subsets.
 
# Function to find the sum
# of sum of all the subset
def SumOfSubset(a, n):
 
    times = pow(2, n - 1)
 
    Sum = 0
 
    for i in range(n):
        Sum = Sum + (a[i] * times)
 
    return Sum
 
# Driver Code
a = [3, 7]
n = len(a)
print(SumOfSubset(a, n))
 
# This code is contributed by Mohit Kumar

// C# program to find the sum of
// the addition of all possible subsets.
using System;
 
class GFG
{
     
// Function to find the sum
// of sum of all the subset
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;
}
 
// Driver Code
public static void Main()
{
    int []a = { 3, 7 };
    int n = a.Length;
    Console.Write(sumOfSubset(a, n));
}
}
 
// This code is contributed by Nidhi

<script>
// javascript program to find the sum of
// the addition of all possible subsets.   
// Function to find the sum
    // of sum of all the subset
    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;
    }
 
    // Driver Code
     
        var a = [ 3, 7 ];
        var n = a.length;
        document.write(sumOfSubset(a, n));
 
// This code is contributed by todaysgaurav
</script>

20

Complejidad de tiempo : O(N) 
Complejidad de espacio : O(1)
Nota : Si N es grande, la respuesta puede desbordarse, por lo que se usa un tipo de datos más grande.