Dada uma matriz de n inteiros não negativos. A tarefa é encontrar a soma do produto dos elementos de todos os subconjuntos possíveis. Pode-se presumir que os números nos subconjuntos são pequenos e o produto computacional não causa estouro aritmético.
Exemplo :
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 Abordagem ingênua: Abordagem simples é gerar todos os subconjuntos possíveis, um por um e calcule a soma de todos os elementos. A complexidade de tempo desta abordagem é exponencial, pois há um total de 2n- 1 subconjunto.
Um Abordagem eficiente é generalizar todo o problema em algum padrão. Suponha que temos dois números a e b. Podemos escrever todos os produtos de subconjuntos possíveis 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
Agora pegue três 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
O padrão acima pode ser generalizado para n números.
Abaixo está a implementação da ideia acima:
C++// C++ program to find sum of product of // all subsets. #include
// 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(0n): 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 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>
Saída
119
Complexidade de tempo: O(n)
Espaço Auxiliar: O(1)
Criar questionário