JavaScriptを使用した組み合わせ合計の問題

候補番号のセット（重複なし）とターゲット番号（ターゲット）が与えられたとします。

候補数の合計がターゲットになる候補内のすべての一意の組み合わせを検索する関数を作成する必要があります。

同じ繰り返し数を候補者から無制限に選択できます。

注 −

• すべての数値（ターゲットを含む）は正の整数になります。

• ソリューションセットに重複する組み合わせを含めることはできません。

例 −

入力が-

candidates = [2,3,6,7], target = 7,

これに対する解決策は次のようになります-

[
   [7],
   [2,2,3]
];

問題は、最良の結果や結果の数ではなく、すべての可能な結果を​​取得することであるため、動的計画法を考慮する必要はありません。それを処理するには、再帰を使用したバックトラックアプローチが必要です。

例

以下はコードです-

const recursiveSum = (
   candidates,
   remainingSum,
   finalCombinations = [],
   currentCombination = [],
   startFrom = 0,
) => {
   if (remainingSum < 0) {
      return finalCombinations;
   }
   if (remainingSum === 0) {
      finalCombinations.push(currentCombination.slice());
      return finalCombinations;
   }
   for (let candidateIndex = startFrom; candidateIndex < candidates.length; candidateIndex += 1) {
      const currentCandidate = candidates[candidateIndex];
      currentCombination.push(currentCandidate);
      recursiveSum(
         candidates,
         remainingSum - currentCandidate,
         finalCombinations,
         currentCombination,
         candidateIndex,
      );
      currentCombination.pop();
   }
   return finalCombinations;
}
const combinationSum = (candidates, target) => recursiveSum(candidates, target);
console.log(combinationSum([2, 3, 6, 7], 7));

出力

以下はコンソールでの出力です-

[ [ 2, 2, 3 ], [ 7 ] ]