JavaScriptでn個の引数の加減算の全組み合わせから0に最も近い合計を求める方法

任意の個数の数値型引数を受け取るJavaScript関数を作成してみましょう。この関数は、各引数に対してプラスとマイナスを割り当てたすべての組み合わせの合計を計算し、その中から0に最も近い値を返します。

例えば、引数が 1, 2, 3 の場合、考えられるすべての組み合わせは以下のとおりです。

1 + 2 + 3
1 - 2 - 3
1 + 2 - 3
1 - 2 + 3

これらの計算結果はそれぞれ 6, -4, 0, 2 となり、0に最も近いのは 0 です。したがって、この場合の答えは 0 となります。

アプローチ：Setを活用した効率的な計算

引数がn個ある場合、符号の組み合わせは2の(n-1)乗通りに達するため、全パターンを素朴に列挙すると計算量が爆発的に増えてしまいます。そこで、Set（集合）を活用して重複する中間結果を除外しながら段階的に計算を進めることで、効率よく答えを導き出せます。

アルゴリズムの手順

1. 最初の引数の絶対値を初期値としてSetに格納します。
2. 2番目以降の各引数について、Set内の既存の値に対して「加算」と「減算」の両方を実行し、その絶対値を新しいSetへ追加します。
3. すべての引数を処理し終えた時点で、Set内の最小値が「0に最も近い合計」になります。

ここで絶対値だけを保持するのは、中間結果 x と -x がその後の演算において必ず絶対値の等しい結果をもたらすためです。符号情報を捨てても最終的な答えには影響せず、管理すべき状態の数を大幅に減らせるという利点があります。

コード例

const findSmallestPositive = (...arr) => {
    let set = new Set([Math.abs(arr[0])]);
    for (let i = 1; i < arr.length; i++){
        const secondSet = new Set;
        for (let d of Array.from(set)){
            secondSet.add(Math.abs(d + arr[i]))
            secondSet.add(Math.abs(d - arr[i]))
        };
        set = secondSet;
    };
    return Math.min(...Array.from(set))
};
console.log(findSmallestPositive(5,3))
console.log(findSmallestPositive(1,2,3))
console.log(findSmallestPositive(1,2,3,5))

出力結果

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

2
0
1

動作の検証

• (5, 3)：5+3=8、5−3=2 のため、0に最も近いのは 2
• (1, 2, 3)：1+2−3=0 となるため、答えは 0
• (1, 2, 3, 5)：1+2+3−5=1 となるため、答えは 1