JavaScript 배열에서 목표 합이 되는 모든 조합 찾기

숫자 배열을 첫 번째 인수로, 목표 합(target sum)을 두 번째 인수로 받는 JavaScript 함수를 작성해야 합니다. 이 함수는 배열의 요소들(중복 사용 여부와 관계없이) 중에서 합이 목표 값과 일치하는 모든 조합을 찾아, 배열 안에 배열 형태로 반환해야 합니다.

예를 들어 입력이 다음과 같다면 −

const arr = [2, 3, 6, 7], sum = 7;

위 입력에 대한 출력은 다음과 같아야 합니다 −

const output = [
   [2, 2, 3],
   [7]
];

접근 방식

이 문제는 백트래킹(backtracking) 기법으로 해결할 수 있습니다. 재귀적으로 각 숫자를 조합에 추가하거나 제외하면서 남은 합(remain)을 추적하고, 남은 합이 0이 되면 해당 경로(path)를 결과에 저장하는 방식입니다.

• 남은 합이 음수가 되면 더 이상 진행할 수 없으므로 탐색을 종료합니다.
• 남은 합이 정확히 0이면 현재까지의 조합을 결과 배열에 추가합니다.
• 같은 숫자를 여러 번 사용할 수 있도록, 재귀 호출 시 시작 인덱스(start)를 그대로 유지합니다.

예제 코드

전체 구현 코드는 다음과 같습니다 −

const arr = [2, 3, 6, 7], sum = 7;
const combineElements = (arr, sum) => {
   const output = [];
   const findCombination = (remain, path, start) => {
      if (remain < 0) {
         return;
      }
      if (remain === 0) {
         output.push([...path]);
         return;
      }
      for (let i = start; i < arr.length; i++) {
         findCombination(remain − arr[i], [...path, arr[i]], i);
      }
   }
   findCombination(sum, [], 0);
   return output;
};
console.log(combineElements(arr, sum));

코드 설명

findCombination 함수는 세 개의 매개변수를 받습니다. remain은 아직 채워야 하는 남은 합, path는 현재까지 선택된 요소들의 조합, start는 탐색을 시작할 인덱스입니다. 반복문에서 i를 start부터 시작함으로써 동일한 조합의 중복 생성을 방지하면서도, 같은 요소의 반복 사용은 허용됩니다. 조합이 완성되면 [...path]로 복사본을 저장하여 이후 재귀 과정에서 원본이 변경되지 않도록 합니다.

출력 결과

콘솔에 출력되는 결과는 다음과 같습니다 −

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