두 개의 정수 n과 k가 주어졌을 때, 1부터 n까지의 숫자 중에서 k개를 선택하여 만들 수 있는 모든 조합을 찾는 문제입니다.
예를 들어 n = 4, k = 2라면 다음과 같은 조합들이 만들어집니다.
[[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]
이 문제는 대표적인 백트래킹(Backtracking) 기법으로 해결할 수 있습니다. 아래에서 풀이 과정과 C++ 구현 예제를 살펴보겠습니다.
풀이 접근 방법
- 재귀 함수
solve()를 사용합니다. 이 함수는 n, k, 임시 배열(temp), 시작 위치(start)를 매개변수로 받으며, start는 처음에 1로 초기화됩니다. - temp 배열의 크기가 k와 같아지면, temp를 결과 배열 res에 추가하고 함수를 종료합니다.
- i를 start부터 n까지 반복하면서 다음 작업을 수행합니다.
- i를 temp 배열에 삽입합니다.
solve(n, k, temp, i + 1)을 재귀 호출합니다.- temp의 마지막 원소를 제거하여 이전 상태로 되돌립니다(백트래킹).
solve(n, k, [])형태로 함수를 최초 호출합니다.- 모든 탐색이 끝나면 res를 반환합니다.
동작 원리
핵심은 각 숫자를 선택할 때마다 현재 값보다 큰 숫자만 다음 후보로 고려한다는 점입니다. 이렇게 하면 [2,1]처럼 순서만 다른 중복 조합이 생성되는 것을 자연스럽게 방지할 수 있습니다. 또한 선택했던 숫자를 다시 제거(pop)함으로써 다른 경로를 탐색할 수 있는데, 이것이 바로 백트래킹의 핵심 동작입니다.
C++ 구현 예제
다음 코드를 통해 실제 구현 방법을 확인해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<int> > 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 n, int k, vector <int> temp, int start = 1){
if(temp.size() == k){
res.push_back(temp);
return;
}
for(int i = start; i <= n; i++){
temp.push_back(i);
solve(n, k, temp, i + 1);
temp.pop_back();
}
}
vector<vector<int> > combine(int n, int k) {
res.clear();
vector <int> temp;
solve(n ,k, temp);
return res;
}
};
main(){
Solution ob;
print_vector(ob.combine(5,3));
}실행 결과 확인
입력
5 3
출력
[[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],[2,3,4],[2,3,5],[2,4,5],[3,4,5]]
n = 5, k = 3인 경우, 1부터 5까지의 숫자 중 3개를 뽑는 총 10가지 조합이 모두 출력되는 것을 확인할 수 있습니다.
시간 복잡도
이 알고리즘의 시간 복잡도는 O(C(n, k) × k)입니다. 생성되는 조합의 개수는 이항 계수 C(n, k)이며, 각 조합을 저장할 때 k개의 원소를 복사하기 때문입니다. 공간 복잡도 역시 결과를 저장하기 위해 O(C(n, k) × k)가 필요하고, 재귀 호출 스택은 최대 깊이 k까지 사용됩니다.