문제 소개
1부터 9까지의 숫자만 사용하여, 합이 특정 값 n이 되는 k개의 숫자 조합을 모두 찾는 문제입니다. 이때 각 조합은 중복 없는 고유한 숫자 집합이어야 하며, 사용되는 모든 숫자는 양수여야 합니다. 또한 동일한 조합이 결과에 두 번 이상 나타나서는 안 됩니다.
예를 들어 k = 3, n = 9가 주어지면 가능한 조합은 [[1,2,6], [1,3,5], [2,3,4]] 세 가지입니다.
알고리즘 접근 방식
이 문제는 대표적인 백트래킹(backtracking) 기법으로 해결할 수 있습니다. 재귀 함수 solve()를 정의하고, 후보 숫자를 하나씩 선택했다가 되돌리는 방식으로 가능한 모든 경우를 탐색합니다.
- solve(k, n, temp, start) 형태의 재귀 메서드를 만듭니다. temp는 지금까지 선택한 숫자를 담는 배열이며, start는 탐색을 시작할 숫자로 초기값은 1입니다.
- n이 0이 되면 다음을 확인합니다.
- temp의 크기가 정확히 k라면 temp를 결과 목록 res에 추가합니다.
- 이후 해당 재귀 호출을 종료합니다.
- n이 0이 아니라면, i를 start부터 min(9, n)까지 반복하면서 다음을 수행합니다.
- i를 temp에 추가합니다.
- solve(k, n − i, temp, i + 1)을 재귀 호출합니다.
- 호출이 끝나면 temp에서 마지막 원소를 제거하여 이전 상태로 되돌립니다(백트래킹).
- 메인 함수에서는 빈 벡터 temp를 생성한 뒤 solve(k, n, temp)를 호출하고, 최종적으로 res를 반환합니다.
재귀 호출 시 start를 i + 1로 전달하기 때문에 한번 사용한 숫자는 다시 선택할 수 없습니다. 또한 항상 오름차순으로만 조합을 만들기 때문에 중복된 조합이 자연스럽게 걸러집니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << "[";
for(int j = 0; j <v[i].size(); j++){
cout << v[i][j] << ", ";
}
cout << "],";
}
cout << "]"<<endl;
}
class Solution {
public:
vector < vector <int> > res;
void solve(int k, int n, vector <int> temp, int start = 1){
if(n == 0){
if(temp.size() == k){
res.push_back(temp);
}
return;
}
for(int i = start ; i <= min(9, n); i++){
temp.push_back(i);
solve(k, n - i, temp, i + 1);
temp.pop_back();
}
}
vector<vector<int>> combinationSum3(int k, int n) {
res.clear();
vector <int> temp;
solve(k, n, temp);
return res;
}
};
main(){
Solution ob;
print_vector(ob.combinationSum3(2, 9));
}
실행 결과
위 코드처럼 k = 2, n = 9로 호출하면 다음과 같은 출력이 나옵니다.
[[1, 8],[2, 7],[3, 6],[4, 5]]
같은 방식으로 k = 3, n = 9를 호출하면 아래와 같은 결과를 얻습니다.
[[1, 2, 6],[1, 3, 5],[2, 3, 4]]
마무리
이 알고리즘은 후보 숫자가 1부터 9까지만 존재하므로 탐색 공간이 매우 작습니다. 따라서 별도의 가지치기 없이도 백트래킹만으로 충분히 빠르게 모든 조합을 찾을 수 있습니다. 핵심은 재귀 호출마다 남은 합(n)을 줄여가고, 시작 인덱스(start)를 증가시켜 중복을 방지하는 것입니다.