JavaScriptで整数配列を同じ平均値を持つ2つのグループに分割できるか判定する方法

問題の概要

JavaScriptで、整数の配列を唯一の引数として受け取る関数を作成することを考えます。この関数の役割は、入力配列の要素を2つのグループに分割したとき、両方のグループの平均値がちょうど等しくなるような組み合わせが存在するかどうかを判定することです。なお、2つのグループに含まれる要素数は同じである必要はありません。

条件を満たす組み合わせが存在すれば関数は true を返し、存在しなければ false を返します。

具体例

たとえば、入力配列が次の場合を考えてみましょう。

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

このときの出力は次の通りです。

const output = true;

その理由は、配列を [8, 1, 5, 4] と [6, 3, 2, 7] の2つのグループに分けると、どちらのグループも平均値が 4.5 となり一致するためです。

実装コード

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

const arr = [6, 3, 2, 8, 1, 5, 7, 4];
const canHaveEqualAveragePartition = (arr = []) => {
    const sum = arr.reduce((acc, val) => acc + val);
    const array = Array(sum+1).fill(false).map(() =>
        Array(arr.length+1).fill(false));
    array[0][0] = true;
    for(let i=0; i < arr.length; ++i){
        for(let j=sum - arr[i]; j>=0; --j){
            for(let k=arr.length-2; k>=0; --k){
                if(array[j][k]){
                    array[j + arr[i]][k+1] = true;
                    if((j + arr[i]) * (arr.length - k - 1) == (sum - j - arr[i]) * (k + 1)){
                        return true;
                    }
                }
            }
        }
    }
    return false;
};
console.log(canHaveEqualAveragePartition(arr));

アルゴリズムの解説

このコードでは動的計画法（DP）を活用しています。処理の流れを整理すると、次のようになります。

• まず、配列全体の合計値 sum を求めます。
• DPテーブル array[j][k] は「いくつかの要素を選んだとき、その合計が j、個数が k になる組み合わせが存在するか」を記録する真偽値です。初期状態として array[0][0] = true（何も選んでいない状態）を設定しておきます。
• 各要素について、既存の部分集合にその要素を追加した状態（合計 j + arr[i]、個数 k + 1）へ DPテーブルを順次更新していきます。
• 更新のたびに、現在の部分集合と残りの要素との間で平均が一致するか、すなわち (部分集合の合計) × (残りの個数) == (残りの合計) × (部分集合の個数) という条件をチェックし、成立すれば true を即座に返します。

この条件式は「部分集合の平均 ＝ 残り要素の平均」という関係を交差掛算の形で表現したものであり、浮動小数点数の誤差を気にせず正確に判定できるのが大きなメリットです。また、ループ変数 k の範囲が arr.length - 2 までに制限されているため、片方のグループが空になるケースは自動的に除外されます。計算量は、要素数を n、合計値を S とすると O(n² × S) 程度になります。

出力結果

コンソールには次のように表示されます。

true