JavaScript로 1~9 숫자를 활용해 합이 n이 되는 m개의 고유 조합 찾기

문제 이해하기

이 함수는 1부터 9 사이의 숫자만 사용하여, 서로 다른 m개의 숫자를 더했을 때 그 합이 정확히 n이 되는 모든 가능한 조합을 찾아야 합니다. 각 조합은 중복 없는 고유한 숫자 집합으로 구성되어야 하며, 하나의 조합 안에서 같은 숫자가 두 번 등장해서는 안 됩니다.

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

const m = 3, n = 4;

출력 결과는 다음과 같습니다 −

const output = [
   [1, 2, 4]
];

또 다른 예시로, 입력값이 다음과 같은 경우 −

const m = 3, n = 9;

출력 결과는 다음과 같습니다 −

const output = [
   [1, 2, 6],
   [1, 3, 5],
   [2, 3, 4]
];

구현 코드

이 문제는 재귀와 백트래킹(backtracking) 기법을 활용하면 효율적으로 해결할 수 있습니다. 전체 코드는 다음과 같습니다 −

const m = 3, n = 9;
const findSum = (m, n) => {
   const search = (from, prefix, m, n) => {
      if (m === 0 && n === 0) return res.push(prefix);
      if (from > 9) return;
      search(from + 1, prefix.concat(from), m − 1, n − from);
      search(from + 1, prefix, m, n);
   };
   const res = [];
   search(1, [], m, n);
   return res;
};
console.log(findSum(m, n));

코드 동작 원리

핵심 역할을 하는 search 함수는 네 가지 매개변수를 받습니다.

• from: 현재 검토 중인 숫자 (탐색 시작점)
• prefix: 지금까지 선택된 숫자들의 목록
• m: 아직 더 선택해야 하는 숫자의 개수
• n: 앞으로 채워야 하는 남은 목표 합

함수의 흐름은 다음과 같습니다.

1. m === 0 && n === 0인 경우, 정확히 m개의 숫자를 모두 골랐고 합도 n에 도달했다는 의미이므로 해당 조합(prefix)을 결과 배열 res에 저장합니다.
2. from > 9인 경우, 사용할 수 있는 숫자(1~9)를 모두 확인한 것이므로 해당 탐색 경로를 종료합니다.
3. 각 단계마다 두 가지 분기를 시도합니다. 첫 번째 호출은 현재 숫자 from을 포함하는 경우(m과 n을 감소), 두 번째 호출은 포함하지 않는 경우입니다.

이러한 이진 분기 구조 덕분에 모든 부분집합을 빠짐없이 탐색하면서도, 이미 조건을 만족하지 못하는 경로는 자연스럽게 가지치기됩니다.

출력 결과

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

[ [ 1, 2, 6 ], [ 1, 3, 5 ], [ 2, 3, 4 ] ]

세 숫자의 합이 9가 되는 모든 고유 조합이 오름차순으로 깔끔하게 출력되는 것을 확인할 수 있습니다.