Suma de los productos de todos los Subconjuntos posibles

Dada una array de n enteros no negativos. La tarea es encontrar la suma del producto de elementos de todos los subconjuntos posibles. Se puede suponer que los números en los subconjuntos son pequeños y que el producto informático no provoca un desbordamiento aritmético.

Ejemplo : 

Input : arr[] = {1, 2, 3}
Output : 23
Possible Subset are: 1, 2, 3, {1, 2}, {1, 3}, 
                     {2, 3}, {1, 2, 3}
Products of elements in above subsets :
1, 2, 3, 2, 3, 6, 6
Sum of all products = 1 + 2 + 3 + 2 + 3 + 6 + 6 
                    = 23

Enfoque ingenuo: el enfoque simple es generar todos los subconjuntos posibles uno por uno y calcular la suma de todos los elementos. La complejidad temporal de este enfoque es exponencial ya que hay un total de 2 ⁿ – 1 subconjuntos.

Un enfoque eficiente es generalizar todo el problema en algún patrón. Supongamos que tenemos dos números a y b. Podemos escribir todos los productos de subconjuntos posibles como: – 

   = a + b + ab 
   = a(1+b) + b + 1 - 1 
   = a(1+b) + (1+b) - 1 
   = (a + 1) * (b + 1) - 1
   = (1+a) * (1 + b) - 1

Ahora toma tres números a, b, c:- 

   = a + b + c + ab + bc + ca + abc 
   = a + ac + b + bc + ab + abc + c + 1 - 1
   = a(1+c) + b(1+c) + ab(1+c) + c + 1 - 1
   = (a + b + ab + 1)(1+c) - 1 
   = (1+a) * (1+b) * (1+c) - 1  

El patrón anterior se puede generalizar para n números.

A continuación se muestra la implementación de la idea anterior: 

// C++ program to find sum of product of
// all subsets.
#include <bits/stdc++.h>
using namespace std;
 
// Returns sum of products of all subsets
// of arr[0..n-1]
int productOfSubsetSums(int arr[], int n)
{
    int ans = 1;
    for (int i = 0; i < n; ++i )
        ans = ans * (arr[i] + 1);
    return ans-1;
}
 
// Driver code
int main()
{
    int arr[] = {1, 2, 3, 4};
    int n = sizeof(arr)/sizeof arr[0];
    cout << productOfSubsetSums(arr, n);
    return 0;
}

// Java program to find sum of product of
// all subsets.
 
public class Subset
{
    // Returns sum of products of all subsets
    // of arr[0..n-1]
    static int productOfSubsetSums(int arr[], int n)
    {
        int ans = 1;
        for (int i = 0; i < n; ++i )
            ans = ans * (arr[i] + 1);
        return ans-1;
    }
     
    public static void main (String[] args)
    {
        int arr[] = {1, 2, 3, 4};
        int n = arr.length;
        System.out.println(productOfSubsetSums(arr, n));
    }
}
 
// This code is contributed by Saket Kumar

# Python3 program to
# find sum of product of
# all subsets.
 
# Returns sum of products
# of all subsets
# of arr[0..n-1]
def productOfSubsetSums(arr, n):
    ans = 1;
    for i in range(0,n):
        ans = ans * (arr[i] + 1)
    return ans-1
 
# Driver code
arr = [1, 2, 3, 4]
n = len(arr)
 
print (productOfSubsetSums(arr, n))
     
# This code is contributed
# by Shreyanshi Arun.

// C# program to find sum of
// product of all subsets.
using System;
 
public class Subset
{
     
    // Returns sum of products of all
    // subsets of arr[0..n-1]
    static int productOfSubsetSums(int []arr, int n)
    {
        int ans = 1;
        for (int i = 0; i < n; ++i )
            ans = ans * (arr[i] + 1);
        return ans-1;
    }
     
    // Driver Code
    public static void Main ()
    {
        int []arr = {1, 2, 3, 4};
        int n = arr.Length;
        Console.Write(productOfSubsetSums(arr, n));
    }
}
 
// This code is contributed by Nitin Mittal.

<?php
// PHP program to find sum of
// product of all subsets.
 
// Returns sum of products of
// all subsets of arr[0..n-1]
function productOfSubsetSums($arr, $n)
{
    $ans = 1;
    for ($i = 0; $i < $n; ++$i )
        $ans = $ans * ($arr[$i] + 1);
    return $ans-1;
}
 
// Driver code
$arr = array(1, 2, 3, 4);
$n = sizeof($arr);
echo(productOfSubsetSums($arr, $n));
 
// This code is contributed by Ajit.
?>

<script>
 
// Javascript program to find sum of product of
// all subsets.
 
// Returns sum of products of all subsets
// of arr[0..n-1]
function productOfSubsetSums(arr, n)
{
    let ans = 1;
    for (let i = 0; i < n; ++i )
        ans = ans * (arr[i] + 1);
    return ans-1;
}
 
// Driver code
 
    let arr = [1, 2, 3, 4];
    let n = arr.length;
    document.write(productOfSubsetSums(arr, n));
 
 
// This code is contributed by Mayank Tyagi
 
</script>

119

Complejidad temporal: O(n) 
Espacio auxiliar: O(1)

Este artículo es una contribución de Shubham Bansal . 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.