Dané pole n nezáporných celých čísel. Úlohou je nájsť súčet súčinov prvkov všetkých možných podmnožín. Dá sa predpokladať, že čísla v podskupinách sú malé a výpočtový produkt nespôsobuje aritmetické pretečenie.
Príklad:
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 Naivný prístup: Jednoduchý prístup je vygenerovať všetky možné podmnožiny jeden po druhom a vypočítajte súčet všetkých prvkov. Časová zložitosť tohto prístupu je exponenciálna, keďže sú celkovo 2n- 1 podskupina.
An Efektívny prístup je zovšeobecniť celý problém do nejakého vzorca. Predpokladajme, že máme dve čísla a a b. Všetky možné produkty podmnožiny môžeme napísať ako: -
= 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
Teraz vezmite tri čísla 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
Vyššie uvedený vzorec možno zovšeobecniť pre n čísel.
Nižšie je uvedená implementácia vyššie uvedenej myšlienky:
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>
Výstup
119
Časová zložitosť: O(n)
Pomocný priestor: O(1)
Vytvoriť kvíz