중복 없는 후보 숫자 배열(candidates)과 목표 숫자(target)가 주어졌다고 가정해 보겠습니다.
우리가 작성해야 할 함수는, 후보 숫자들을 더했을 때 목표 숫자가 되는 모든 고유한 조합을 찾아내는 것입니다.
여기서 흥미로운 점은 같은 숫자를 제한 없이 몇 번이고 반복해서 선택할 수 있다는 것입니다.
문제 조건
- 모든 숫자(목표 숫자 포함)는 양의 정수입니다.
- 결과 집합에는 중복된 조합이 포함되어서는 안 됩니다.
예시
다음과 같은 입력이 주어졌을 때 −
candidates = [2,3,6,7], target = 7,
정답은 다음과 같습니다 −
[ [7], [2,2,3] ];
[2,2,3]처럼 숫자 2를 여러 번 재사용하는 것이 허용되며, [2,3,2]와 같은 순서만 다른 조합은 별도의 정답으로 간주하지 않습니다.
접근 방식: 왜 백트래킹인가?
이 문제는 최적의 단일 결과를 찾거나 결과의 개수만 세는 것이 아니라, 가능한 모든 조합을 전부 나열해야 하는 문제입니다. 따라서 동적 계획법(Dynamic Programming)은 적합하지 않으며, 재귀를 활용한 백트래킹(Backtracking) 기법으로 해결하는 것이 자연스럽습니다.
백트래킹의 핵심 아이디어는 다음과 같습니다.
- 후보 숫자를 하나씩 현재 조합에 추가하며 남은 합(remainingSum)을 줄여 나갑니다.
- 남은 합이 0이 되면 유효한 조합을 하나 찾은 것이므로 결과에 저장합니다.
- 남은 합이 음수가 되면 더 이상 진행할 수 없으므로 해당 경로를 포기하고 이전 상태로 되돌아갑니다(백트래킹).
- 중복 조합을 방지하기 위해 탐색 시작 인덱스(startFrom)를 관리하여 항상 현재 위치 이후의 숫자만 선택합니다.
구현 코드
다음은 위 로직을 자바스크립트로 구현한 코드입니다 −
const recursiveSum = (
candidates,
remainingSum,
finalCombinations = [],
currentCombination = [],
startFrom = 0,
) => {
// 남은 합이 음수면 이 경로는 유효하지 않음
if (remainingSum < 0) {
return finalCombinations;
}
// 남은 합이 정확히 0이면 유효한 조합 발견
if (remainingSum === 0) {
finalCombinations.push(currentCombination.slice());
return finalCombinations;
}
// startFrom부터 탐색하여 중복 조합 방지
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 ] ]
핵심 포인트 정리
- currentCombination.slice(): 참조가 아닌 복사본을 저장해야 이후의 pop() 연산으로 인해 결과가 오염되지 않습니다.
- candidateIndex를 그대로 재귀에 전달: 같은 숫자의 반복 선택을 허용하면서도, 이전 인덱스로 돌아가지 않게 하여 중복 조합([2,3,2] 등)을 차단합니다.
- push 후 pop: 선택과 선택 취소를 반복하는 백트래킹의 전형적인 패턴입니다.
이처럼 백트래킹은 '모든 경우의 수 탐색'이 필요한 조합 문제에서 가장 널리 쓰이는 강력한 기법이므로, 이 코드의 흐름을 잘 이해해 두면 유사한 문제(순열, 부분집합, N-Queens 등)에도 손쉽게 응용할 수 있습니다.