พิจารณาว่าเรามีอาร์เรย์ A ที่มี n องค์ประกอบ เราต้องหาผลรวมรวมของผลรวมของทุกเซตย่อยของอาร์เรย์ ดังนั้นถ้าอาร์เรย์เป็น A = [5, 6, 8] จะเป็นดังนี้:
| Subset | Sum |
|---|---|
| 5 | 5 |
| 6 | 6 |
| 8 | 8 |
| 5,6 | 11 |
| 6,8 | 14 |
| 5,8 | 13 |
| 5,6,8 | 19 |
| Total Sum | 76 |
เนื่องจากอาร์เรย์มี n องค์ประกอบ เราจึงมีจำนวนเซตย่อย 2^n เซต (รวมเซตว่าง) หากเราสังเกตอย่างชัดเจน เราจะพบว่าแต่ละองค์ประกอบเกิดขึ้น 2^(n-1) ครั้ง
ตัวอย่างโค้ด C++
#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;
}
ผลลัพธ์
Total sum of the sum of all subsets: 76
