C++で指定された条件に従って配列を合計が等しい2つの部分に分割する方法

ここでは一つの問題を取り上げます。ある配列 arr が与えられたとき、その配列が以下の条件をすべて満たす形で2つの部分に分割できるかどうかを判定する必要があります。

• 両方の部分配列の要素の合計が等しくなること
• 5の倍数であるすべての要素は、必ず同じグループに属すること
• 3の倍数だが5の倍数ではないすべての要素も、必ず同じグループに属すること
• 上記以外の要素は、どちらのグループに配置しても構わないこと

例として、配列の要素が {1, 4, 3} である場合を考えてみましょう。この場合は分割が可能です。なぜなら、{1, 3} の合計（4）と {4} の合計（4）が等しく、さらに5の倍数・3の倍数に関するグループ分けの条件も正しく満たされているからです。

アルゴリズム

isSplitArray(arr, n, start, left_sum, right_sum) の擬似コードは以下の通りです。

Begin
    if start = n, then return true when left_sum = right_sum, otherwise false
    if arr[start] is divisible by 5, then add arr[start] with the left_sum
    else if arr[start] is divisible by 3, then add arr[start] with the right_sum
    else
        return isSplitArray(arr, n, start + 1, left_sum + arr[start], right_sum) OR 
               isSplitArray(arr, n, start + 1, left_sum, right_sum + arr[start])
    isSplitArray(arr, n, start + 1, left_sum, right_sum)
End

アルゴリズムのポイント

• 配列の末尾（start = n）に到達した時点で、左右の合計が一致していれば true を返します。
• 5の倍数の要素は自動的に left_sum 側へ、3の倍数（ただし5の倍数を除く）の要素は自動的に right_sum 側へ振り分けられます。
• どちらの倍数でもない要素については、左側・右側の両方のケースを再帰的に試すことで、全ての組み合わせを網羅的に探索します。

C++による実装例

#include <iostream>
using namespace std;
bool isSplitArray(int* arr, int n, int start, int left_sum, int right_sum) {
    if (start == n) // 配列の末尾に到達したとき
        return left_sum == right_sum;
    if (arr[start] % 5 == 0) // 要素が5で割り切れる場合、左側の合計に加算
        left_sum += arr[start];
    else if (arr[start] % 3 == 0) // 要素が3で割り切れるが5では割り切れない場合、右側の合計に加算
        right_sum += arr[start];
    else // それ以外の場合は、どちらの部分配列にも追加できる
        return isSplitArray(arr, n, start + 1, left_sum + arr[start], right_sum) || isSplitArray(arr, n, start + 1, left_sum, right_sum + arr[start]);
    // 要素が3または5の倍数だった場合の処理
    return isSplitArray(arr, n, start + 1, left_sum, right_sum);
}
int main() {
    int arr[] = {1, 4, 3};
    int n = sizeof(arr)/sizeof(arr[0]);
    if(isSplitArray(arr, n, 0, 0, 0)){
        cout << "Can be split";
    } else {
        cout << "Can not be split";
    }
}

出力結果

Can be split

この実装では、再帰呼び出しによって制約のない要素の割り当てパターンを全て試行するため、配列の長さに対して指数的な計算量となります。しかし、条件付きのグループ分けを伴うこの種の分割問題では、シンプルで理解しやすいアプローチとして有効です。