C++에서 배열의 모든 부분 집합 합의 총합 구하기

n개의 요소를 가진 배열 A가 있다고 가정해 보겠습니다. 이때 우리가 구해야 할 값은 배열의 모든 부분 집합(subset)의 합들을 다시 한 번 모두 더한 총합입니다.

예를 들어 배열이 A = [5, 6, 8]이라면, 만들 수 있는 부분 집합과 각각의 합은 다음과 같습니다.

핵심 아이디어: 각 원소의 등장 횟수

배열의 원소 개수가 n개일 때, 만들 수 있는 부분 집합의 개수는 공집합을 포함하여 2ⁿ개입니다. 여기서 중요한 관찰은 다음과 같습니다.

모든 부분 집합을 나열했을 때, 각 원소는 정확히 2^n-1번 등장합니다.

왜냐하면 특정 원소를 기준으로 볼 때, 그 원소를 포함하는 부분 집합의 개수는 나머지 n-1개 원소로 만들 수 있는 부분 집합의 개수(2^n-1)와 같기 때문입니다.

따라서 전체 총합은 다음 공식으로 간단하게 계산할 수 있습니다.

총합 = (배열 원소들의 합) × 2^n-1

위 예제에서는 (5 + 6 + 8) × 2² = 19 × 4 = 76으로, 표의 결과와 일치합니다. 이 방법을 사용하면 부분 집합을 하나씩 생성하지 않고도 O(n) 시간 복잡도로 답을 구할 수 있습니다.

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 << "모든 부분 집합 합의 총합: " << totalSum(arr, n) << endl;
}

실행 결과

모든 부분 집합 합의 총합: 76

코드 설명

totalSum 함수는 먼저 반복문을 통해 배열의 모든 원소의 합을 구한 뒤, 여기에 2^n-1을 곱해 최종 결과를 반환합니다. pow(2, n - 1) 함수는 cmath 헤더에 정의되어 있어 지수 계산에 활용됩니다.

이처럼 수학적 규칙을 발견하면, 무작정 모든 경우를 탐색하는 O(2ⁿ) 방식 대신 훨씬 효율적인 선형 시간 알고리즘으로 문제를 해결할 수 있습니다.