พิจารณาว่าเรามีอาร์เรย์ A ที่มี n องค์ประกอบ เราต้องหาผลรวมของผลรวมของเซตย่อยทั้งหมดของอาร์เรย์ ดังนั้นหากอาร์เรย์เป็นเหมือน A =[5, 6, 8] ก็จะเป็นเช่น −
| ชุดย่อย | ผลรวม |
|---|---|
| 5 | 5 |
| 6 | 6 |
| 8 | 8 |
| 5,6 | 11 |
| 6,8 | 14 |
| 5,8 | 13 |
| 5,6,8 | 19 |
| ผลรวมทั้งหมด | 76 |
เนื่องจากอาร์เรย์มีองค์ประกอบ n รายการ เราจึงมีชุดย่อยจำนวน 2n ชุด (รวมค่าว่างด้วย) หากสังเกตให้ชัดจะพบว่าแต่ละองค์ประกอบเกิดขึ้น 2n-1 ครั้ง
ตัวอย่าง
#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
