조합 생성 알고리즘 한번에 정리하기

▶조합 (Combination)

---

서로 다른 n개의 원소 중에 r개를 순서와 상관 없이 뽑은 것을 조합이라고 합니다.

뽑아낼 수 있는 조합의 모든 경우를 알아내야 하는 문제들이 많습니다.

기본적인 구현 문제이지만 공부하지 않으면 어떻게 구현해야 할지 몰라 막막하게 느껴지기도 합니다.

조합을 코드로 구현하기 위해서 재귀 함수에 익숙해질 필요가 있습니다.

재귀함수를 이해하기 위해 백준 온라인 저지에서 '피보나치 수를 구하는 문제'나 'N과 M'과 같은 문제들을 풀면서 재귀함수에 익숙해지도록 연습하는 것을 추천합니다.

#include<iostream>
#include<vector>
using namespace std;
 
int n,r;
vector<int> vt, tmp;
 
//idx는 vt의 인덱스를 나타냄
void combination(int idx){
    if(tmp.size() == r){
        // r개의 원소를 모두 선택한 경우
        for(int num: tmp){
            cout<<num<<" ";
        }
        cout<<"\n";
        return;
    }
    
    if(idx == n) 
        return;
 
    tmp.push_back(vt[idx]);
    combination(idx+1);
    tmp.pop_back();
    combination(idx+1);
}
int main(){
    cin>>n>>r;
    for(int i=0,k; i<n; i++){
        cin>>k;
        vt.push_back(k);
    }
    combination(0);
    return 0;
}

핵심이 되는 것은 원소를 선택 후 재귀호출, 원소를 선택하지 않은 채로 재귀호출하는 부분입니다.

line	설명
29 ~ 32	벡터 vt에 서로다른 n개의 원소를 입력 받습니다.
22 ~ 23	vt[idx]를 임시 저장하고, vt의 다음 원소 위치를 가리키는 idx+1를 인자로 넘겨 재귀 호출 합니다. (원소 선택 후 재귀호출)
24 ~ 25	임시저장했던 vt[idx]를 삭제하고, vt의 다음 원소 위치를 가리키는 idx+1를 인자로 넘겨 재귀호출 합니다. (원소 선택하지 않은 채로 재귀호출)
19 ~ 20	idx가 n이 되면 원소를 가리키는 인덱스의 범위를 초과하게 되므로 함수를 종료합니다.

[입력]
n : 5 

r : 3
원소 : 1 2 3 4 5

[실행 결과]