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

問題概要

整数の配列を唯一の引数として受け取るJavaScript関数を作成します。この関数の役割は、元の配列のすべての要素を使い切り、かつ各サブ配列の要素の合計が等しくなるように、配列を2つのサブ配列へ分割できるかどうかを判定することです。分割の際、元の配列の要素が1つも残らないようにする点が重要です。

つまり、この問題は「配列を2つのグループに振り分けたとき、両グループの合計値が一致する組み合わせが存在するか」を確認するものです。

入力例

const arr = [5, 3, 7, 4, 1, 8, 2, 6];

出力例

const output = true;

この場合、[5, 3, 4, 6] と [7, 1, 8, 2] という2つのサブ配列に分割でき、どちらも合計が18で一致するため、結果は true となります。

解法のアプローチ：動的計画法

この問題は古典的なパーティション問題（部分和問題）として知られており、動的計画法（DP）を使うことで効率的に解けます。考え方は以下の通りです。

• まず配列全体の合計を求めます。合計が奇数であれば、2つの等しい部分に分けることは不可能なので、即座に false を返します。
• 合計が偶数であれば、「合計の半分（target）」となる部分集合が作れるかどうかをDPで判定します。
• DPテーブル array[i] は「一部の要素を選んで合計 i を作れるかどうか」を表す真偽値として管理します。

コード例

以下が実際のコードです。

const arr = [5, 3, 7, 4, 1, 8, 2, 6];
const canPartition = (arr = []) => {
    const sum = arr.reduce((acc, val) => acc + val);
    if (sum % 2 !== 0){
        return false;
    };
    const target = sum / 2;
    const array = new Array(target + 1).fill(false);
    array[0] = true;
    for (const num of arr) {
        if (array[target - num]){
            return true
        };
        for (let i = target; i >= num; i--) {
            array[i] = array[i - num];
        }
    }
    return false;
};
console.log(canPartition(arr));

実行結果

コンソールへの出力は以下の通りです。

true

コードの解説

1. 合計の計算： reduce() メソッドで配列全体の合計 sum を求めます。
2. 奇数チェック： 合計が奇数なら2等分は不可能なため、その時点で false を返します。
3. DPテーブルの初期化： サイズ target + 1 の真偽値配列を用意し、array[0] = true（何も選ばなければ合計0は必ず作れる）とします。
4. DPテーブルの更新： 各要素 num について、target から num まで逆順にループし、array[i - num] が true なら array[i] を更新します。逆順に処理することで、同じ要素の二重使用を防げます。
5. 早期リターン： 処理中に合計 target の達成が確認できたら、即座に true を返すことで無駄な計算を省いています。

計算量

• 時間計算量：O(n × sum / 2) — 要素数 n と目標合計に比例します。
• 空間計算量：O(sum / 2) — DPテーブルのサイズのみ必要です。

全要素の組み合わせを総当たりするブルートフォース方式（O(2^n)）に比べ、動的計画法を用いることで大幅に計算量を抑えられるのがこの手法の大きな利点です。