Tìm tổng của tổng của tất cả các chuỗi con trong C ++

Xét chúng ta có một mảng A với n phần tử. Ta phải tìm tổng của tổng của tất cả các tập con của mảng. Vì vậy, nếu mảng giống như A =[5, 6, 8], thì nó sẽ giống như -

Khi mảng có n phần tử, thì chúng ta có 2n số tập con (bao gồm cả tập trống). Nếu quan sát rõ ràng, chúng ta có thể thấy rằng mỗi phần tử xuất hiện 2n-1 lần

Ví dụ

#include<iostream>
#include<cmath>
using namespace std;
int totalSum(int arr[], int n) {
   int res = 0;
   for (int i = 0; i < n; i++)
      res += arr[i];
   return res * pow(2, n - 1);
}
int main() {
   int arr[] = { 5, 6, 8 };
   int n = sizeof(arr)/sizeof(arr[0]);
   cout << "Total sum of the sum of all subsets: " << totalSum(arr, n) << endl;
}

Đầu ra

Total sum of the sum of all subsets: 76