1. 문제 정의
중복되지 않는 양의 정수 배열 candidates와 양의 정수 target이 주어졌을 때, 합이 target이 되는 모든 고유한 조합을 찾는 문제입니다. 배열의 각 요소는 무제한으로 재사용할 수 있으며, 요소의 순서만 다른 조합은 동일한 것으로 간주합니다. 이 문제의 핵심은 최적의 해를 찾는 것이 아니라 조건을 만족하는 모든 해를 탐색하는 것이므로, 백트래킹이 기본적인 해결 방법이 됩니다.
2. 기본 접근법: 단순 백트래킹
2.1 알고리즘 개요
백트래킹은 '시도-검증-되돌리기' 과정을 반복하는 탐색 방법입니다. 이 문제에 가장 직접적인 구현 방식은 배열의 첫 번째 요소부터 시작하여 각 요소를 현재 경로에 추가하고, 남은 목표 값을 재귀적으로 검증하는 것입니다. 조건을 만족하지 못하면 요소를 제거하고 다음 요소를 시도합니다.
2.2 기본 구현 코드
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> results;
vector<int> current;
backtrack(candidates, target, 0, current, results);
return results;
}
void backtrack(vector<int>& candidates, int remaining, int start,
vector<int>& current, vector<vector<int>>& results) {
if (remaining == 0) {
results.push_back(current);
return;
}
for (int i = start; i < candidates.size(); ++i) {
int val = candidates[i];
if (val > remaining) {
continue; // 현재 요소만 건너뛰고 계속 진행
}
current.push_back(val);
backtrack(candidates, remaining - val, i, current, results);
current.pop_back();
}
}
};
2.3 기본 구현의 한계
- 정렬이 되어 있지 않아,
val > remaining조건을 만나더라도 이후 요소들을 계속 검사해야 합니다. 따라서 불필요한 재귀 호출이 많이 발생합니다. candidates의 값 범위가 넓거나target이 큰 경우, 성능 저하가 심각해집니다.
3. 1차 최적화: 정렬과 가지치기
3.1 최적화 아이디어
기본 구현의 단점을 해결하기 위해 다음과 같은 전처리 과정을 도입합니다.
candidates를 오름차순으로 정렬합니다. 정렬된 상태에서는 특정 요소가 남은 목표 값보다 클 경우, 그 이후의 모든 요소도 목표 값보다 크기 때문에 반복문을 즉시 종료할 수 있습니다.start인덱스를 재귀 호출 시 그대로 전달하여 요소의 무제한 재사용을 허용하면서도[2, 3]과[3, 2]같은 중복 조합을 방지합니다.
3.2 최적화된 코드
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> results;
vector<int> current;
sort(candidates.begin(), candidates.end()); // 전처리: 정렬
backtrack(candidates, target, 0, current, results);
return results;
}
void backtrack(vector<int>& candidates, int remaining, int start,
vector<int>& current, vector<vector<int>>& results) {
if (remaining == 0) {
results.push_back(current);
return;
}
for (int i = start; i < candidates.size(); ++i) {
int val = candidates[i];
if (val > remaining) {
break; // 가지치기: 더 이상 검사할 필요 없음
}
current.push_back(val);
backtrack(candidates, remaining - val, i, current, results);
current.pop_back();
}
}
};
3.3 최적화 효과 분석
정렬의 시간 복잡도는 O(n log n)이며 한 번만 수행됩니다. 가지치기를 통해 불필요한 재귀 호출이 크게 줄어들어, 실제 실행 시간이 몇 배에서 수십 배까지 빨라질 수 있습니다. 최악의 경우 시간 복잡도는 여전히 해 공간의 크기(O(S), S는 모든 유효 조합의 길이 합)에 의해 결정되지만, 평균적인 성능은 크게 개선됩니다.
4. 고급 최적화: 수치적 특성 활용
4.1 최적화 아이디어
정렬과 가지치기 외에도 추가적인 전처리를 통해 탐색 범위를 더욱 줄일 수 있습니다.
target보다 큰 요소는 애초에 사용될 수 없으므로, 후보 배열에서 제외합니다.- 현재 경로의 합을 별도 변수로 관리하여 매번
target - sum(current)을 계산하는 비용을 줄입니다. - 특정 요소를 여러 번 사용할 수 있다는 점을 이용해, 해당 요소를 한 번에 최대 몇 개까지 사용할 수 있는지(
max_count = (target - current_sum) / val) 미리 계산하고, 이를 한 번의 재귀 호출 내에서 처리합니다.
4.2 고급 최적화 코드
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> results;
vector<int> current;
// 1. target보다 큰 요소 미리 제거
vector<int> filtered;
for (int num : candidates) {
if (num <= target) {
filtered.push_back(num);
}
}
// 2. 정렬
sort(filtered.begin(), filtered.end());
// 3. 개선된 백트래킹
backtrack(filtered, target, 0, 0, current, results);
return results;
}
void backtrack(vector<int>& candidates, int target, int start,
int current_sum, vector<int>& path, vector<vector<int>>& results) {
if (current_sum == target) {
results.push_back(path);
return;
}
for (int i = start; i < candidates.size(); ++i) {
int val = candidates[i];
// 현재 합에 val을 더했을 때 target을 초과하면 중단
if (current_sum + val > target) {
break;
}
// val을 최대 몇 번 사용할 수 있는지 계산
int max_count = (target - current_sum) / val;
for (int count = 1; count <= max_count; ++count) {
// count 만큼 val을 경로에 추가
for (int j = 0; j < count; ++j) {
path.push_back(val);
}
// 재귀 호출 (다음 인덱스부터 시작하여 중복 방지)
backtrack(candidates, target, i + 1,
current_sum + count * val, path, results);
// 추가한 val들을 다시 제거
for (int j = 0; j < count; ++j) {
path.pop_back();
}
}
}
}
};
4.3 최적화 로직 설명
- 대량 처리: 같은 요소를 여러 번 사용할 때, 각각의 반복 횟수에 대해 개별적인 재귀 호출을 하는 대신, 가능한 모든 반복 횟수를 한 번에 처리합니다. 이렇게 하면 재귀 호출 깊이가 줄어들고, 특히
target이 크고val이 작을 때 성능 향상이 뚜렷합니다. - 사전 필터링:
target보다 큰 요소를 미리 제거하여 탐색해야 할 요소 수를 줄입니다. - 합계 변수 관리:
current_sum변수를 사용하여 매번target - sum(path)를 계산하는 오버헤드를 없앴습니다.
5. 엔지니어링 구현 고려 사항
5.1 자료 구조 선택
- 경로 저장:
vector<int>는push_back과pop_back이 O(1)의 시간 복잡도를 가지며, 메모리가 연속적으로 할당되어 캐시 효율이 좋습니다. - 결과 저장:
vector<vector<int>>는 대부분의 시나리오에 적합합니다. 중복 제거가 필요하다면unordered_set을 사용할 수 있지만, 해시 함수를 직접 정의해야 하는 등 구현이 복잡해집니다. - 입력 데이터 보존: 원본 배열을 수정하지 않고
filtered와 같은 별도 배열을 사용하는 것이 좋은 엔지니어링 관행입니다.
5.2 확장성 설계
- 백트래킹 로직을 별도 함수로 분리하여 재사용성과 가독성을 높입니다.
- 변수명(
start,current_sum등)을 명확하게 지정하여 유지보수를 용이하게 합니다. - 경계 조건에 대한 처리를 추가합니다:
if (candidates.empty() || target <= 0) { return results; }
5.3 성능과 가독성의 균형
- 고급 최적화는 성능을 향상시키지만 코드 복잡도를 증가시킵니다. 작은 입력(
candidates의 크기가 작거나target이 작은 경우)에는 단순한 정렬 + 가지치기만으로도 충분합니다. - 과도한 최적화는 피해야 합니다. 예를 들어, 반복문으로 재귀를 대체하면 스택 오버플로우를 방지할 수 있지만, 코드 가독성이 크게 떨어집니다. 성능 병목이 명확하게 확인된 경우에만 시도하는 것이 좋습니다.
5.4 병렬화 가능성
백트래킹 탐색은 본질적으로 직렬적이지만, 분할 정복 방식을 적용할 수 있습니다. 예를 들어, candidates 배열을 여러 개의 하위 배열로 나누고, 각 하위 배열의 첫 번째 요소로 시작하는 조합을 별도 스레드에서 탐색한 후 결과를 병합하는 방법입니다. 이 때는 결과의 중복을 피하기 위한 동기화(예: 뮤텍스)가 필요하며, 이로 인한 오버헤드가 병렬화의 이점을 상쇄할 수 있으므로 매우 큰 입력에 대해서만 고려하는 것이 좋습니다.
6. 결론
조합 합계 문제는 백트래킹 알고리즘의 전형적인 예시입니다. 기본적인 해결 방법은 '선택-재귀-되돌리기'의 패턴을 따르며, start 인덱스를 통해 중복 조합을 방지합니다. 성능 최적화는 정렬을 통한 가지치기에서 시작하여, 수치적 특성을 활용한 사전 필터링과 대량 처리로 발전할 수 있습니다. 실제 엔지니어링 환경에서는 코드의 가독성, 유지보수성, 그리고 성능 간의 균형을 맞추는 것이 중요하며, 과도한 최적화보다는 명확하고 확장 가능한 코드를 작성하는 데 집중해야 합니다.