C++で配列のすべての部分集合の合計値を効率的に求める方法

n個の要素を持つ配列Aが与えられたとき、その配列のすべての部分集合の合計値の総和を求める問題を考えてみましょう。

例えば、配列が A = [5, 6, 8] の場合、各部分集合とその合計は以下のようになります。

考え方のポイント

n個の要素を持つ配列の場合、部分集合の数は（空集合を含めて）2ⁿ 個存在します。

ここで重要な性質に注目してみましょう。各要素は、ちょうど 2⁽ⁿ⁻¹⁾ 回だけ部分集合に出現するという点です。

この性質を利用すると、すべての部分集合の合計値の総和は次の式で一発に計算できます。

総和 = （配列の全要素の合計） × 2^(n-1)

つまり、部分集合を実際に列挙して足し合わせる必要はなく、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];
    // 全要素の合計に 2^(n-1) を掛ける
    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

まとめ

この問題は、各要素が 2⁽ⁿ⁻¹⁾ 回出現するという数学的な性質を利用することで、部分集合を全列挙することなく効率的に解くことができます。計算量は O(n) であり、要素数が多い配列でも高速に動作します。なお、n が大きい場合はオーバーフローに注意し、必要に応じて long long 型などの使用を検討してください。