코딩테스트-조합

C++로 조합(Combination) 구현하기 — 그리고 언제 이중 포문 대신 재귀를 쓸까

순열(Permutation)이 "순서가 있는 나열"이라면, 조합(Combination)은 "순서 없이 뽑기"다. 예를 들어 {1,2,3}에서 2개를 뽑을 때 (1,2)와 (2,1)은 같은 것으로 본다. 이번 글에서는 재귀로 조합을 구현하고, 왜 이중 포문보다 재귀가 나은 경우가 있는지 정리한다.

---

1. 조합 공식 (nCr)

조합의 개수는 다음 공식으로 구한다.

       n!
nCr = --------
      r!(n-r)!

• nCr : 조합의 수
• n : 집합의 전체 원소 개수
• r : 뽑을 원소 개수

하지만 우리가 필요한 건 "개수"만이 아니라 "실제 조합 목록"인 경우가 많다. 그래서 재귀로 직접 나열해 본다.

---

2. 재귀를 이용한 조합 구현

#include <bits/stdc++.h>

using namespace std;
int n = 5, k = 3, a[5] = {1, 2, 3, 4, 5}; // a는 예시일 뿐이다.

void print(vector<int> b){
    for(int i : b){
        cout << i << " ";
    }
    cout << "\n";
}

void combi(int start, vector<int> b){
    if(b.size() == k){   // k개를 다 뽑았으면 하나의 조합 완성
        print(b);
        return;
    }
    for(int i = start + 1; i < n; i++){
        b.push_back(i);   // i번째 원소를 뽑고
        combi(i, b);      // 그 다음(i)부터 이어서 뽑는다
        b.pop_back();     // 원상 복구 (백트래킹)
    }
    return;
}

int main()
{
    vector<int> b;
    combi(-1, b);
    return 0;
}

실제 값을 출력하고 싶다면

위 코드는 인덱스(0~4)를 저장·출력한다. 즉 {1,2,3,4,5}가 아니라 0 1 2처럼 인덱스가 찍힌다. 배열의 실제 값을 뽑으려면 아래처럼 a[i]를 저장하면 된다.

void combi(int start, vector<int> b){
    if(b.size() == k){
        print(b);
        return;
    }
    for(int i = start + 1; i < n; i++){
        b.push_back(a[i]);  // 인덱스가 아니라 실제 값 저장
        combi(i, b);
        b.pop_back();
    }
    return;
}

동작 원리

• start: "이 다음 인덱스부터 골라라"는 기준점. 이미 고른 것보다 뒤에서만 고르게 해서 중복과 순서 뒤바뀜을 원천 차단한다.
• for(i = start+1; ...): 항상 앞에서 고른 것보다 큰 인덱스만 선택 → (2,1) 같은 역순 조합이 생기지 않는다.
• b.size() == k: k개를 다 채우면 하나의 조합이 완성된 것이므로 출력.
• push_back → 재귀 → pop_back: 골랐다가 다시 빼는 백트래킹 패턴.

처음에 combi(-1, b)로 시작하는 이유는, start + 1 = 0이 되어 0번 인덱스부터 탐색을 시작하기 위함이다.

호출 흐름 시각화

C(start, {고른 것들}) 형태로 호출이 뻗어나가는 모습을 그려보면, 깊이 우선(DFS)으로 한 갈래를 끝까지 파고든 뒤(빨간 화살표: 재귀 진입) 다시 위로 돌아와(파란 화살표: 백트래킹) 다음 갈래로 넘어가는 구조가 보인다. 재귀 조합의 핵심은 결국 "골랐다가 되돌리기"의 반복이다.

---

3. 언제 이중 포문 대신 재귀를 써야 할까?

이게 이번 글의 핵심이다. 결론부터 말하면 "뽑을 개수 r이 고정되어 있지 않거나 클 때" 재귀가 압도적으로 유리하다.

이중 포문의 한계

3개 중 2개를 뽑는 조합은 이중 포문으로 쉽게 짤 수 있다.

for(int i = 0; i < n; i++)
    for(int j = i + 1; j < n; j++)
        cout << a[i] << " " << a[j] << "\n";

그런데 3개를 뽑으려면 삼중 포문, 4개면 사중 포문이 필요하다. 즉 뽑는 개수 r만큼 for문을 손으로 늘려야 한다. 이건 다음과 같은 치명적 문제가 있다.

• r이 변수면 아예 불가능 — "사용자가 입력한 r개를 뽑아라"를 for문 중첩으로는 짤 수 없다. 중첩 깊이는 컴파일 시점에 고정되기 때문이다.
• 코드 중복과 실수 — r이 커질수록 i < j < k < l ... 조건을 일일이 관리해야 해서 버그가 늘어난다.
• 가독성 붕괴 — 5중, 6중 포문은 사실상 유지보수 불가.

재귀의 장점

반면 재귀는 r(=k)이 몇이든 코드가 그대로다. 위 combi 함수는 k 값만 바꾸면 2개든 5개든 10개든 동일하게 동작한다. for문 중첩을 재귀 호출 깊이로 대체하기 때문이다.

기준	이중(다중) 포문	재귀
뽑는 개수 r	컴파일 시점에 고정 (변경 불가)	런타임 변수로 자유롭게 지정
r이 2~3개로 작고 고정	간결하고 빠름 (추천)	다소 오버스펙
r이 크거나 가변	사실상 불가능	유일한 현실적 해법
가독성 / 확장성	r 커질수록 급격히 나빠짐	r과 무관하게 일정

정리하면

• r이 2~3으로 작고 고정이면 → 이중/삼중 포문이 더 직관적이고 빠르다.
• r이 4 이상이거나, r이 변수로 주어지면 → 재귀(또는 next_permutation 응용)가 정답이다.

실전 코딩 테스트에서 "N개 중 M개를 고르는데 M이 입력값"이라면 고민할 것 없이 재귀 백트래킹으로 가는 것이 안전하다.

---

마무리

조합 재귀의 핵심은 딱 두 가지다. (1) start로 뒤쪽 원소만 고르게 해 중복을 막는다. (2) push_back → 재귀 → pop_back으로 골랐다 되돌린다. 이 패턴만 손에 익히면 순열, 조합, 부분집합 문제 대부분을 같은 틀로 풀 수 있다.