Suma de cuadrados de todos los subconjuntos de array dada

Dada una array arr[] . El valor de un subconjunto de la array A se define como la suma de los cuadrados de todos los números de ese subconjunto. La tarea es calcular la suma de los valores de todos los posibles subconjuntos no vacíos de la array dada. 
Dado que la respuesta puede ser en letra grande el val mod 1000000007.
Ejemplos: 
 

Entrada: arr[] = {3, 7} 
Salida: 116 
val({3}) = 3 ² = 9 
val({7}) = 7 ² = 49 
val({3, 7}) = 3 ² + 7 ² = 9 + 49 = 58 
9 + 49 + 58 = 116
Entrada: arr[] = {1, 1, 1} 
Salida: 12 
 

Enfoque ingenuo: un enfoque simple es encontrar todo el subconjunto y luego elevar al cuadrado cada elemento en ese subconjunto y agregarlo al resultado. La complejidad temporal de este enfoque será O(2 ^N )
Enfoque eficiente: se puede observar que en todos los subconjuntos posibles del arreglo dado, cada elemento aparecerá 2 ^{N – 1} veces donde N es el tamaño del arreglo. 
Entonces la contribución de cualquier elemento X en la suma será 2 ^{N – 1} * X ² .
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
const int mod = 1e9 + 7;
 
// Function to return (2^P % mod)
long long power(int p)
{
    long long res = 1;
    for (int i = 1; i <= p; ++i) {
        res *= 2;
        res %= mod;
    }
    return res % mod;
}
 
// Function to return the sum of squares of subsets
long long subset_square_sum(vector<int>& A)
{
 
    int n = (int)A.size();
 
    long long ans = 0;
 
    // Sqauaring the elements
    // and adding it to ans
    for (int i : A) {
        ans += (1LL * i * i) % mod;
        ans %= mod;
    }
 
    return (1LL * ans * power(n - 1)) % mod;
}
 
// Driver code
int main()
{
    vector<int> A = { 3, 7 };
 
    cout << subset_square_sum(A);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
    static final int mod = (int)(1e9 + 7);
     
    // Function to return (2^P % mod)
    static long power(int p)
    {
        long res = 1;
        for (int i = 1; i <= p; ++i)
        {
            res *= 2;
            res %= mod;
        }
        return res % mod;
    }
     
    // Function to return the sum of squares of subsets
    static long subset_square_sum(int A[])
    {
        int n = A.length;
     
        long ans = 0;
     
        // Sqauaring the elements
        // and adding it to ans
        for (int i : A)
        {
            ans += (1 * i * i) % mod;
            ans %= mod;
        }
        return (1 * ans * power(n - 1)) % mod;
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int A[] = { 3, 7 };
     
        System.out.println(subset_square_sum(A));
    }
}
 
// This code is contributed by AnkitRai01

# Python3 implementation of the approach
mod = 10**9 + 7
 
# Function to return (2^P % mod)
def power(p):
 
    res = 1
    for i in range(1, p + 1):
        res *= 2
        res %= mod
 
    return res % mod
 
# Function to return the sum of
# squares of subsets
def subset_square_sum(A):
 
    n = len(A)
 
    ans = 0
 
    # Squaring the elements
    # and adding it to ans
    for i in A:
        ans += i * i % mod
        ans %= mod
 
    return ans * power(n - 1) % mod
 
# Driver code
A = [3, 7]
 
print(subset_square_sum(A))
 
# This code is contributed by Mohit Kumar

// C# implementation of the approach
using System;
     
class GFG
{
    static readonly int mod = (int)(1e9 + 7);
     
    // Function to return (2^P % mod)
    static long power(int p)
    {
        long res = 1;
        for (int i = 1; i <= p; ++i)
        {
            res *= 2;
            res %= mod;
        }
        return res % mod;
    }
     
    // Function to return the sum of squares of subsets
    static long subset_square_sum(int []A)
    {
        int n = A.Length;
     
        long ans = 0;
     
        // Sqauaring the elements
        // and adding it to ans
        foreach (int i in A)
        {
            ans += (1 * i * i) % mod;
            ans %= mod;
        }
        return (1 * ans * power(n - 1)) % mod;
    }
     
    // Driver code
    public static void Main (String[] args)
    {
        int []A = { 3, 7 };
     
        Console.WriteLine(subset_square_sum(A));
    }
}
     
// This code is contributed by 29AjayKumar

<script>
// Javascript implementation of the approach
 
const mod = 1000000000 + 7;
 
// Function to return (2^P % mod)
function power(p)
{
    let res = 1;
    for (let i = 1; i <= p; ++i) {
        res *= 2;
        res %= mod;
    }
    return res % mod;
}
 
// Function to return the sum of squares of subsets
function subset_square_sum(A)
{
 
    let n = A.length;
 
    let ans = 0;
 
    // Sqauaring the elements
    // and adding it to ans
    for (let i = 0; i < n; i++) {
        ans += (A[i] * A[i]) % mod;
        ans %= mod;
    }
 
    return (ans * power(n - 1)) % mod;
}
 
// Driver code
    let A = [ 3, 7 ];
 
    document.write(subset_square_sum(A));
</script>

116

Complejidad de tiempo: O(N)

Espacio Auxiliar: O(1)