자바스크립트를 사용한 콤비네이션 문제

후보 번호 세트(중복 없음)와 대상 번호(대상)가 주어진다고 가정합니다.

우리는 후보 숫자의 합이 목표값인 후보에서 모든 고유한 조합을 찾는 함수를 작성해야 합니다.

동일한 반복 번호는 후보자 중에서 무제한으로 선택될 수 있습니다.

참고 -

• 모든 숫자(대상 포함)는 양의 정수입니다.

• 솔루션 세트는 중복 조합을 포함할 수 없습니다.

예를 들어 -

입력이 -

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 ] ]