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

本記事では、数値の配列 arr を第一引数、整数 num を第二引数として受け取るJavaScript関数の実装方法を解説します。

この関数の目的は、配列の要素を num 個のグループに分配したとき、すべてのグループの合計が等しくなるような分割方法が存在するかどうかを判定することです。分割方法が存在する場合は true を、存在しない場合は false を返します。

問題の例

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

const arr = [4, 6, 3, 3, 7, 4, 1];
const num = 4;

この場合の出力は次のようになります。

const output = true;

true が返される理由は、要素を以下の4つのグループに分けると、それぞれの合計がすべて7で等しくなるためです。

• [7]
• [1, 6]
• [4, 3]
• [4, 3]

実装コード

この問題を解くコードは以下の通りです。

const arr = [4, 6, 3, 3, 7, 4, 1];
const num = 4;
const canDivide = (arr = [], num = 1) => {
   const sum = arr.reduce((acc, num) => acc + num);
   if (sum % num !== 0 || arr.some(num => num > sum / num)) {
      return false;
   }
   const used = new Set();
   return (function find(start, target) {
      if (used.size === arr.length) {
         return true;
      }
      if (target < 0) {
         return false;
      }
      if (target === 0) {
         return find(0, sum / num);
      }
      for (let i = start; i < arr.length; i++) {
         if (!used.has(i)) {
            used.add(i);
            if (find(i + 1, target - arr[i])) {
               return true;
            }
            used.delete(i);
         }
      }
      return false;
   })(0, sum / num);
};
console.log(canDivide(arr,num));

アルゴリズムの解説

このソリューションでは、以下の手順で処理を行っています。

1. 事前チェック: 配列の合計値が num で割り切れない場合、または配列内のいずれかの要素が sum / num（各グループの目標値）より大きい場合は、分割が不可能なため即座に false を返します。
2. 使用済み要素の管理: Set（HashSet）を使用して、すでにグループに割り当てられた要素のインデックスを追跡します。
3. バックトラッキング探索: 再帰的に部分集合を組み立てていきます。具体的には以下の条件で分岐します。
   • すべての要素を使い切ったら、分割成功として true を返します。
   • 現在の部分集合の合計が目標値を超えたら、その経路の探索を打ち切ります。
   • 部分集合の合計がちょうど目標値に達したら、次のグループの探索に移ります。
4. 全要素の試行: 最後に、未使用のすべての要素を順番に試し、有効な分割が見つかるまで探索を続けます。

このアプローチは「バックトラッキング」と呼ばれる手法で、Partition to K Equal Sum Subsets として知られる古典的な問題の標準的な解法です。計算量は最悪情况下 O(2^n) となりますが、事前チェックや枝刈りにより多くの場合で高速に動作します。

実行結果

上記のコードをコンソールで実行すると、次の出力が得られます。

true

この結果から、配列 [4, 6, 3, 3, 7, 4, 1] の要素を、合計が等しい4つのグループに分割できることが確認できます。