조합(Combination) 재귀함수 및 반복문 구현

조합

조합이란 유한 개의 원소에서 주어진 수만큼의 원소들을 고르는 방법을 말한다.
n개 중에서 순서에 상관없이 r개를 뽑는 경우에 사용한다.

경우의 수를 구하는 공식은 아래와 같다.

       $_nC_r = \frac{n!}{r!(n - r)!}$

🔎 반복문을 이용한 구현

중복을 허용하지 않고 순서에 상관이 없으므로 중첩 for문을 통해 쉽게 구현이 가능하다.

코드 구현

#include <bits/stdc++.h>
using namespace std;
int n = 5, k = 3;

int main() {
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			for (int k = j + 1; k < n; k++) {
				cout << i << " " << j << " " << k << "\n";
			}
		}
	}
	return 0;
}

실행 결과

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

🔎 재귀함수를 이용한 구현

재귀함수를 이용해서도 조합을 구현해 낼 수 있다.

구현 원리

사실상 중첩 for문과 크게 다른 점이 없다.
앞 자리부터 하나씩 반복문을 통해 순서대로 벡터에 넣으면서
그 다음 자리부터 재귀함수를 호출하고
벡터의 크기가 r이 되면 리턴한다
리턴 후에는 벡터에 넣었던 함수를 다시 뺀다.

코드 구현

#include <bits/stdc++.h>
using namespace std;
int n = 5, r = 3;

void combi(int start, vector<int> a) {
	if (a.size() == r) {
		for (auto i : a) {
			cout << i << " ";
		}
		cout << "\n";
		return;
	}
	for (int i = start; i < n; i++) {
		a.push_back(i);
		combi(i + 1, a);
		a.pop_back();
	}
	return;
}
int main() {
	vector<int> b;
	combi(0, b);
	return 0;
}

실행 결과

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