C++で配列を合計が等しい2つのサブ配列に分割できるか判定する方法

問題の概要

配列 A が与えられたとき、その配列を「合計が等しい2つのサブ配列」に分割できるかどうかを判定します。例えば、要素が [6, 1, 3, 2, 5] の配列であれば、[6, 1] と [2, 5] という2つのサブ配列に分けることができ、それぞれの合計はどちらも 7 で等しくなります。

アルゴリズムの考え方

この問題は、次の手順に従うことで簡単に解くことができます。

1. まず、配列内の全要素の合計(total_sum)を求めます。
2. 次に、配列を先頭から順に走査しながら、それまでに読み取った要素の累積和(so_far_sum)を更新していきます。
3. 各位置 i において、「2 × so_far_sum + arr[i] == total_sum」という条件が成立するかどうかを確認します。この条件が真になれば、その位置を境界として左右の合計が一致するため、配列を2つのサブ配列に分割できます(この実装では、境界となる要素 arr[i] 自体はどちら側のサブ配列にも含まれません)。

最後まで走査しても条件が一度も成立しなかった場合は、合計が等しい2つのサブ配列には分割できないと判断します。

C++による実装例

#include <iostream>
#include <numeric>
using namespace std;

void displaySubArray(int arr[], int left, int right) {
    cout << "[ ";
    for (int i = left; i <= right; i++)
        cout << arr[i] << " ";
    cout << "] ";
}

void subarrayOfSameSum(int arr[], int n) {
    int total_sum = accumulate(arr, arr + n, 0);
    int so_far_sum = 0;
    for (int i = 0; i < n; i++) {
        if (2 * so_far_sum + arr[i] == total_sum) {
            cout << "subarray 1: ";
            displaySubArray(arr, 0, i - 1);
            cout << "\nsubarray 2: ";
            displaySubArray(arr, i + 1, n - 1);
            return;
        }
        so_far_sum += arr[i];
    }
    cout << "No subarray can be formed";
}

int main() {
    int arr[] = {6, 1, 3, 2, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    subarrayOfSameSum(arr, n);
}

実行結果

subarray 1: [ 6 1 ]
subarray 2: [ 2 5 ]

計算量

この手法の時間計算量は O(n)、空間計算量は O(1) です。全体の合計を事前に求めておけば、累積和を更新しながら1回の走査だけで判定が完了するため、非常に効率的なアプローチです。