n개의 요소가 있는 배열 A가 있다고 가정해 보겠습니다. 배열의 모든 부분집합의 합계의 총합을 찾아야 합니다. 따라서 배열이 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