Suma de todos los subconjuntos de un conjunto formado por los primeros n números naturales

Dado un número n, necesitamos encontrar la suma de todos los elementos de todos los subconjuntos posibles de un conjunto formado por los primeros n números naturales.
Ejemplos: 
 

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)

Una solución simple es generar todos los subconjuntos . Para cada subconjunto, calcule su suma y finalmente devuelva la suma total.
Una solución eficiente se basa en el hecho de que todo número del 1 al n aparece exactamente 2 ^(n-1) veces. Entonces nuestra suma requerida es (1 + 2 + 3 + ..+ n) * 2 ^(n-1) . La suma se puede escribir como (n * (n + 1)/2) * 2 ^(n-1)
 

// 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 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.

# 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# 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 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
?>

<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>

Producción : 

24

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)

Este artículo es una contribución de Raj Kumar . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.