所有可能子集的乘积之和-yiteyi-C++库

给定n个非负整数的数组。其任务是求所有可能子集的元素乘积之和。可以假设子集中的数字很小，计算乘积不会导致算术溢出。 例子：

null

Input : arr[] = {1, 2, 3}Output : 23Possible 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, 6Sum of all products = 1 + 2 + 3 + 2 + 3 + 6 + 6                     = 23

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

天真的方法： 简单的方法是逐个生成所有可能的子集计算所有元素的和。这种方法的时间复杂度是指数的，因为总共有2个 ^N –1个子集。一 有效的方法 就是把整个问题归纳成某种模式。假设我们有两个数字a和b。我们可以把所有可能的子集积写成：-

   = 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

现在取三个数字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

上述模式可以推广到n个数。以下是上述理念的实施：

C++

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

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

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

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

Javascript

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

输出：

时间复杂性： O（n） 辅助空间： O（1）本文由 Shubham Bansal .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用贡献极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章