Suma de subconjuntos de todos los subconjuntos de una array | O(2^N)

Dada una array arr[] de longitud N , la tarea es encontrar la suma total de los subconjuntos de todos los subconjuntos de la array.
Ejemplos: 
 

Entrada: arr[] = {1, 1} 
Salida: 6 
Todos los subconjuntos posibles: 
a) {} : 0 
Todos los subconjuntos posibles de este subconjunto 
serán {}, Sum = 0 
b) {1} : 1 
Todos los subconjuntos posibles de este subconjunto 
serán {} y {1}, Sum = 0 + 1 = 1 
c) {1} : 1 
Todos los posibles subconjuntos de este subconjunto 
serán {} y {1}, Sum = 0 + 1 = 1 
d ) {1, 1} : 4 
Todos los subconjuntos posibles de este subconjunto 
serán {}, {1}, {1} y {1, 1}, Suma = 0 + 1 + 1 + 2 = 4 
Así, ans = 0 + 1 + 1 + 4 = 6
Entrada: arr[] = {1, 4, 2, 12} 
Salida: 513 
 

Enfoque: En este artículo, se discutirá  un enfoque con complejidad de tiempo O(N * 2 ^N ) para resolver el problema dado.
Primero, genere todos los subconjuntos posibles de la array. Habrá 2 ^N subconjuntos en total. Luego, para cada subconjunto, encuentre la suma de todos sus subconjuntos.
Pues, se puede observar que en un arreglo de longitud L , cada elemento vendrá exactamente 2 ^{(L – 1)} veces en la suma de subconjuntos. Entonces, la contribución de cada elemento será 2 ^{(L – 1)} veces sus valores.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to sum of all subsets of a
// given array
void subsetSum(vector<int>& c, int& ans)
{
    int L = c.size();
    int mul = (int)pow(2, L - 1);
    for (int i = 0; i < c.size(); i++)
        ans += c[i] * mul;
}
 
// Function to generate the subsets
void subsetGen(int* arr, int i, int n,
               int& ans, vector<int>& c)
{
    // Base-case
    if (i == n) {
 
        // Finding the sum of all the subsets
        // of the generated subset
        subsetSum(c, ans);
        return;
    }
 
    // Recursively accepting and rejecting
    // the current number
    subsetGen(arr, i + 1, n, ans, c);
    c.push_back(arr[i]);
    subsetGen(arr, i + 1, n, ans, c);
    c.pop_back();
}
 
// Driver code
int main()
{
    int arr[] = { 1, 1 };
    int n = sizeof(arr) / sizeof(int);
 
    // To store the final ans
    int ans = 0;
    vector<int> c;
 
    subsetGen(arr, 0, n, ans, c);
    cout << ans;
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
// To store the final ans
static int ans;
 
// Function to sum of all subsets of a
// given array
static void subsetSum(Vector<Integer> c)
{
    int L = c.size();
    int mul = (int)Math.pow(2, L - 1);
    for (int i = 0; i < c.size(); i++)
        ans += c.get(i) * mul;
}
 
// Function to generate the subsets
static void subsetGen(int []arr, int i,
                      int n, Vector<Integer> c)
{
    // Base-case
    if (i == n)
    {
 
        // Finding the sum of all the subsets
        // of the generated subset
        subsetSum(c);
        return;
    }
 
    // Recursively accepting and rejecting
    // the current number
    subsetGen(arr, i + 1, n, c);
    c.add(arr[i]);
    subsetGen(arr, i + 1, n, c);
    c.remove(0);
}
 
// Driver code
public static void main(String []args)
{
    int arr[] = { 1, 1 };
    int n = arr.length;
 
    Vector<Integer> c = new Vector<Integer>();
 
    subsetGen(arr, 0, n, c);
    System.out.println(ans);
}
}
 
// This code is contributed by 29AjayKumar

# Python3 implementation of the approach
 
# store the answer
c = []
ans = 0
 
# Function to sum of all subsets of a
# given array
def subsetSum():
    global ans
    L = len(c)
    mul = pow(2, L - 1)
    i = 0
    while ( i < len(c)):
        ans += c[i] * mul
        i += 1
         
# Function to generate the subsets
def subsetGen(arr, i, n):
 
    # Base-case
    if (i == n) :
 
        # Finding the sum of all the subsets
        # of the generated subset
        subsetSum()
        return
     
    # Recursively accepting and rejecting
    # the current number
    subsetGen(arr, i + 1, n)
    c.append(arr[i])
    subsetGen(arr, i + 1, n)
    c.pop()
 
# Driver code
if __name__ == "__main__" :
 
    arr = [ 1, 1 ]
    n = len(arr)
 
    subsetGen(arr, 0, n)
    print (ans)
     
# This code is contributed by Arnab Kundu

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG
{
 
// To store the final ans
static int ans;
 
// Function to sum of all subsets of a
// given array
static void subsetSum(List<int> c)
{
    int L = c.Count;
    int mul = (int)Math.Pow(2, L - 1);
    for (int i = 0; i < c.Count; i++)
        ans += c[i] * mul;
}
 
// Function to generate the subsets
static void subsetGen(int []arr, int i,
                      int n, List<int> c)
{
    // Base-case
    if (i == n)
    {
 
        // Finding the sum of all the subsets
        // of the generated subset
        subsetSum(c);
        return;
    }
 
    // Recursively accepting and rejecting
    // the current number
    subsetGen(arr, i + 1, n, c);
    c.Add(arr[i]);
    subsetGen(arr, i + 1, n, c);
    c.RemoveAt(0);
}
 
// Driver code
public static void Main(String []args)
{
    int []arr = { 1, 1 };
    int n = arr.Length;
 
    List<int> c = new List<int>();
 
    subsetGen(arr, 0, n, c);
    Console.WriteLine(ans);
}
}
 
// This code is contributed by Rajput-Ji

<script>
// javascript implementation of the approach
 
    // To store the final ans
    var ans = 0;
 
    // Function to sum of all subsets of a
    // given array
    function subsetSum( c) {
        var L = c.length;
        var mul = parseInt( Math.pow(2, L - 1));
        for (i = 0; i < c.length; i++)
            ans += c[i] * mul;
    }
 
    // Function to generate the subsets
    function subsetGen(arr , i , n, c) {
        // Base-case
        if (i == n) {
 
            // Finding the sum of all the subsets
            // of the generated subset
            subsetSum(c);
            return;
        }
 
        // Recursively accepting and rejecting
        // the current number
        subsetGen(arr, i + 1, n, c);
        c.push(arr[i]);
        subsetGen(arr, i + 1, n, c);
        c.pop(0);
    }
 
    // Driver code
     
        var arr = [ 1, 1 ];
        var n = arr.length;
 
        var c = [];
 
        subsetGen(arr, 0, n, c);
        document.write(ans);
 
// This code is contributed by todaysgaurav
</script>

6