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

問題の概要

JavaScriptで、第1引数に整数の配列、第2引数に整数を受け取る関数を作成する必要があります。

この関数の役割は、元の配列を第2引数で指定された個数（n個）のサブ配列（部分集合）に分割できるかどうかを判定することです。ただし、重要な条件として、すべてのサブ配列の合計値が等しくなければなりません。

入出力の例

たとえば、次のような入力が与えられたとします。

const arr = [4, 3, 2, 3, 5, 2, 1];
const num = 4;

この場合の出力は true になります。理由は、この配列を [5]、[1, 4]、[2, 3]、[2, 3] の4つのサブ配列に分割でき、それぞれの合計がすべて「5」で等しいためです。

解決アプローチ

この問題は「k個の部分集合への等分割問題」として知られる古典的なアルゴリズム問題で、バックトラッキング（探索の巻き戻し） を使うのが定番の解法です。考え方は以下の手順になります。

1. まず、配列全体の合計値を求めます。
2. 合計がnで割り切れない場合、等しい合計のサブ配列には絶対に分割できないため、その時点で false を返して終了します。
3. 各サブ配列の目標値（target）は「合計 ÷ n」で計算できます。
4. 各要素を「使用済みかどうか」のフラグで管理しながら、目標値に到達する要素の組み合わせを再帰的に探索します。

コード例

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

const arr = [4, 3, 2, 3, 5, 2, 1];
const num = 4;
const canFormSubarray = (arr = [], num) => {
    const total = arr.reduce((sum, num) => sum + num, 0);

    if (total % num !== 0) {
        return false;
    }
    const target = total / num;
    const visited = new Array(arr.length).fill(false);
    const canPartition = (start, numberOfSubsets, currentSum) => {
        if (numberOfSubsets === 1) {
            return true;
        }
        if (currentSum === target) {
            return canPartition(0, numberOfSubsets - 1, 0);
        };
        for (let i = start; i < arr.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                if (canPartition(i + 1, numberOfSubsets, currentSum + arr[i])) {
                    return true;
                }
                visited[i] = false;
            };
        };
        return false;
    };
    return canPartition(0, num, 0);
};
console.log(canFormSubarray(arr, num));

コードのポイント解説

• total： reduce() メソッドで配列全体の合計値を算出しています。
• target： 各サブ配列が満たすべき合計値です。「total % num !== 0」の場合は分割不可能なので即座に false を返します。
• visited： 各要素がすでに使用されたかどうかを記録する真偽値の配列で、同じ要素の二重使用を防ぎます。
• canPartition： 再帰的にサブ配列を構築する内部関数です。現在の合計（currentSum）がtargetに達したら、次のサブ配列の構築へ移ります。残りが1グループだけなら残りの要素で必ず成立するため true を返します。探索に失敗した場合はフラグを戻して（バックトラックして）別の組み合わせを試します。

出力結果

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

true