[Algorithm] 조합(Combination) 구현 코드

인트로

본 포스팅에선 조합을 구하는 코드를 소개하려 한다. 결론부터 말하면 재귀 함수(DFS)로 조합을 구할 수 있다.

 

조합이란 n개 중에 r개를 "순서에 무관하게" 뽑는 경우의 수로 다음과 같이 표현한다. $_nC_r=\frac{n!}{(n-r)!r!}$

이와 유사하게 순서를 고려해 n개 중에 r개를 뽑는 것을 순열이라고 한다.

 

※참고 - 순열 포스팅

[Algorithm] 순열(Permutation) 구현 코드

조합 : 코드

순서에 무관하게 숫자를 뽑기때문에 별도의 visited 배열이 필요하지 않다.

#include <iostream>
using namespace std;

int arr[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int cnt, n, r;
int order[4];

void combination(int now, int pos)
{
	if (now == r)
	{
		for (int i = 0; i < r; i++)
		{
			cout << arr[order[i]] << " ";
		}
		cout << endl;
		cnt++;

		return;
	}

	for (int idx = pos; idx < n; idx++)
	{
		order[now] = idx;
		combination(now + 1, idx + 1);
	}
}

int main()
{
	cout << "n : ";
	cin >> n;
	cout << "r : ";
	cin >> r;
	cout << n << 'C' << r << endl;

	combination(0, 0);
	cout << "조합의 개수 : " << cnt;
}