[C++] 재귀함수를 이용한 조합

조합(combination)은 특정 집합에서 순서를 고려하지 않고 선택한 부분집합을 의미합니다. 

이 글에서는 재귀함수를 이용한 조합 생성 코드를 설명합니다.

함수 정의

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(i);
        combi(i, b);
        b.pop_back();
    }
}

주요 요소

• start: 현재 조합에서 다음 요소를 선택하기 시작할 위치를 의미합니다.
• b: 현재까지 선택된 요소들을 저장하는 벡터입니다.
• k: 선택할 요소의 개수입니다.
• n: 선택 가능한 전체 요소의 개수입니다.
• print(b): 완성된 조합을 출력하는 함수입니다.

작동 원리

1. 조합의 완성 조건:
   • if (b.size() == k) 부분에서 현재 조합이 완성되었는지 확인합니다. 조합의 길이가 원하는 길이 k에 도달하면 print(b)를 호출하여 조합을 출력합니다.
2. 재귀 호출을 통한 조합 생성:
   • for (int i = start + 1; i < n; i++) 반복문을 통해 현재 요소 다음의 요소들을 순회합니다.
   • b.push_back(i)를 통해 현재 요소 i를 조합에 추가합니다.
   • combi(i, b)를 재귀 호출하여 다음 요소를 추가합니다.
   • b.pop_back()를 통해 마지막에 추가한 요소를 제거하여 다음 반복을 준비합니다.

예제 코드

다음은 위 함수와 함께 사용할 수 있는 예제 코드입니다:

#include <bits/stdc++.h>
using namespace std;

int n, k;

void print(const vector<int>& b) {
    for (int num : b) {
        cout << num << ' ';
    }
    cout << endl;
}

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(i);
        combi(i, b);
        b.pop_back();
    }
}

int main() {
    n = 5;  // 예: n = 5
    k = 3;  // 예: k = 3
    vector<int> b;
    combi(-1, b);  // 초기 start 값은 -1 (첫 번째 요소가 0부터 시작하게 하기 위함)
    return 0;
}

코드 설명

1. 메인 함수 설정:
   • n과 k 값을 설정합니다. 여기서는 n = 5와 k = 3으로 설정하였습니다.
   • vector<int> b는 현재 조합을 저장할 벡터입니다.
   • combi(-1, b)를 호출하여 조합 생성을 시작합니다. -1을 시작값으로 하여 첫 번째 요소가 0부터 시작하도록 합니다.
2. 조합 생성 및 출력:
   • combi 함수는 재귀적으로 호출되며, b.size()가 k에 도달할 때마다 print 함수가 호출되어 조합을 출력합니다.
   • print 함수는 벡터 b의 모든 요소를 출력합니다.

조합 생성의 예

n = 5와 k = 3인 경우, 생성되는 조합은 다음과 같습니다:

0 1 2
0 1 3
0 1 4
0 2 3
0 2 4
0 3 4
1 2 3
1 2 4
1 3 4
2 3 4

함수 동작의 도식화

다음은 n = 5, k = 3인 경우의 재귀 호출 과정을 도식화한 것입니다:

combi(-1, [])
  ├ combi(0, [0])
  |   ├ combi(1, [0, 1])
  |   |   ├ combi(2, [0, 1, 2])  -> print [0, 1, 2]
  |   |   ├ combi(3, [0, 1, 3])  -> print [0, 1, 3]
  |   |   └ combi(4, [0, 1, 4])  -> print [0, 1, 4]
  |   ├ combi(2, [0, 2])
  |   |   ├ combi(3, [0, 2, 3])  -> print [0, 2, 3]
  |   |   └ combi(4, [0, 2, 4])  -> print [0, 2, 4]
  |   └ combi(3, [0, 3])
  |       └ combi(4, [0, 3, 4])  -> print [0, 3, 4]
  ├ combi(1, [1])
  |   ├ combi(2, [1, 2])
  |   |   ├ combi(3, [1, 2, 3])  -> print [1, 2, 3]
  |   |   └ combi(4, [1, 2, 4])  -> print [1, 2, 4]
  |   └ combi(3, [1, 3])
  |       └ combi(4, [1, 3, 4])  -> print [1, 3, 4]
  └ combi(2, [2])
      └ combi(3, [2, 3])
          └ combi(4, [2, 3, 4])  -> print [2, 3, 4]

결론

재귀함수를 이용한 조합 생성은 C++에서 매우 직관적이고 이해하기 쉬운 방법입니다. 이를 통해 원하는 길이의 조합을 효율적으로 생성하고 출력할 수 있습니다. 이러한 방법은 알고리즘 문제 해결 및 조합론적 문제를 풀 때 매우 유용합니다.