【JavaScript】配列から長さnの組み合わせをすべて生成し、それぞれの合計を求める方法

本記事では、数値の配列を第1引数に、整数 n を第2引数として受け取るJavaScript関数の作成方法を解説します。ここで n は、常に配列の長さ以下であると仮定します。

この関数の役割は、元の配列から長さ n の部分配列として考えられるすべての組み合わせを抽出し、それぞれの要素の合計値をまとめた配列として返すことです。

入力例と出力例

たとえば、次のような入力が与えられた場合を考えてみましょう。

const arr = [2, 6, 4];
const n = 2;

このとき、長さ2の部分配列として取り得るのは [2, 6]、[2, 4]、[6, 4] の3通りです。それぞれの合計は 8、6、10 となるため、出力は次のようになります(結果の並び順は実装によって異なる場合があります)。

const output = [8, 10, 6];

ビット演算を使った実装

すべての組み合わせを網羅的に生成するには、ビットマスクを利用する方法が有効です。配列の各要素を「ビットのオン・オフ」に対応させることで、2ⁿ 通りの選択パターンをすべて走査できます。

具体的なコードは以下のとおりです。

const arr = [2, 6, 4];
const n = 2;
const buildCombinations = (arr, num) => {
    const res = [];
    let temp, i, j, max = 1 << arr.length;
    for(i = 0; i < max; i++){
        temp = [];
        for(j = 0; j < arr.length; j++){
            if (i & 1 << j){
                temp.push(arr[j]);
            };
        };
        if(temp.length === num){
            res.push(temp.reduce(function (a, b) { return a + b; }));
        };
    };
    return res;
}
console.log(buildCombinations(arr, n));

コードのポイント解説

• 1 << arr.length:配列の長さを m とすると、2^m 通りのビットパターン(部分集合の総数)を表します。
• i & 1 << j:整数 i の j 番目のビットが立っているかどうかを判定し、立っていれば対応する要素 arr[j] を一時配列に追加します。
• temp.length === num:選ばれた要素数が指定した n と一致する場合のみ、reduce() を使って合計値を計算し、結果配列に格納します。

実行結果

コンソールには次のように出力されます。並び順はビットマスクの走査順序に依存します。

[ 8, 6, 10 ]

補足:計算量に関する注意点

この手法の計算量は O(2ⁿ × n) であり、配列が長くなるほど処理時間は急激に増加します。要素数が少ないケースではシンプルで扱いやすい反面、大規模な配列を扱う場合は、再帰によるバックトラッキングなど、条件を満たさない組み合わせを早期に枝刈りできるアルゴリズムへの置き換えを検討するとよいでしょう。