Gegeven een array van n niet-negatieve gehele getallen. De taak is om de som te vinden van het product van elementen van alle mogelijke deelverzamelingen. Er mag worden aangenomen dat de getallen in subsets klein zijn en dat computerproducten geen rekenkundige overflow veroorzaken.
Voorbeeld :
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 Naïeve aanpak: Een eenvoudige aanpak is om genereer alle mogelijke subsets één voor één en bereken de som van alle elementen. De tijdscomplexiteit van deze aanpak is exponentieel, aangezien er in totaal 2 zijnN- 1 subsets.
Een Efficiënte aanpak is om het hele probleem in een bepaald patroon te generaliseren. Stel dat we twee getallen a en b hebben. We kunnen alle mogelijke deelverzamelingsproducten schrijven als: -
= 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
Neem nu drie getallen 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
Het bovenstaande patroon kan worden gegeneraliseerd voor n getallen.
Hieronder ziet u de implementatie van bovenstaand idee:
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>
Uitvoer
119
Tijdcomplexiteit: O(n)
Hulpruimte: O(1)
Quiz maken