Cho mảng A n phần tử. Tìm tổng của tổng tất cả tập con của mảng. Nếu 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 |
Mảng n phần tử có 2ⁿ tập con (kể rỗng). Quan sát thấy mỗi phần tử xuất hiện 2ⁿ⁻¹ lần.
Ví dụ mã nguồn
#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; } Kết quả
Total sum of the sum of all subsets: 76