C ++中所有可能子集的乘积之和

在这个问题中，我们得到了N个数字的数组arr []。我们的任务是创建一个程序，该程序将查找所有可能子集的乘积之和。

在这里，我们将找到所有子集，然后找到每个子集的所有元素的乘积。然后将所有值相加以计算总和。

让我们举个例子来了解这个问题，

输入值

arr[] = {4, 5, 6}

输出结果

209

说明-

All subsets of arr[] are: {4}, {5}, {6}, {4, 5}, {5, 6}, {4, 6}, {4, 5, 6}
Sum of product
= (4) + (5) + (6) + (4*5) + (5*6) + (4*6) + (4*5*6)
= (4) + (5) + (6) + (20) + (30) + (24) + (120)
= 209

解决该问题的一种简单方法是找到集合的所有子集并计算每个集合的元素乘积。并将所有乘积相加，遍历所有子集后返回所有最终和。

示例

该程序说明了我们解决方案的工作原理，

#include<iostream>
#include<math.h>
using namespace std;
int findSumProductSubset(int *arr, int set_length) {
   unsigned int size = pow(2, set_length);
   int sum = 0;
   int product;
   for(int counter = 1; counter < size; counter++) {
      product = 1;
      for(int j = 0; j < size; j++) {
         if(counter & (1<<j))
         product *= arr[j];
      }
      sum += product;
   }
   return sum;
}
int main() {
   int arr[] = {4, 5, 6};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout<<"The sum of the product of all subsets is "<<findSumProductSubset(arr, n);
}

输出结果

The sum of the product of all subsets is 209

上述方法生成所有子集，因此具有指数时间复杂度。因此，这不是最有效的方法。

一种更有效的方法是找到解决方案的模式。

现在，让我们看一下三个数字x，y，z的集合。

总和= x + y + z + xy + yz + xz + xyz

和= x + xz + y + yz + xy + xyz + z +1-1

和= x（1 + z）+ y（1 + z）+ xy（1 + z）+ 1（z + 1）-1

总和=（x + y + xy + 1）（1 + z）-1

总和=（x（1 + y）+ 1（1 + y））（1 + z）-1

总和=（1 + x）*（1 + y）*（1 + z）-1

可以通过以下方式归纳如下：

对于n个元素集，

总和=（1+ e1）*（1 + e2）*…*（1 + en）-1

示例

该程序说明了我们解决方案的工作原理，

#include <iostream>
using namespace std;
int productOfSubsetSums(int arr[], int n) {
   int sum = 1;
   for (int i = 0; i < n; ++i )
   sum *= (arr[i] + 1);
   sum --;
   return sum;
}
int main() {
   int arr[] = {5, 6, 8 , 9};
   int n = sizeof(arr)/sizeof arr[0];
   cout<<"Sum of product of all possible subsets is "<<productOfSubsetSums(arr, n);
   return 0;
}

输出结果

Sum of product of all possible subsets is 3779