[Algorithm] 조합 알고리즘 - Combination Algorithm

조합을 구하는 공식이다.

nCr = n-1Cr-1 + n-1Cr

원소가 1,2,3 에서 2개를 골라내는 조합이라고 치자.

(1,2) (2,3) (1,3) 세개지 경우가 있는데 이는 다음과 같은 경우 두가지로 쪼개진다.

(1,X) 인 경우와

(X,X) 인 경우이다.

첫번째 경우는 1이 확정되었으므로, 나머지 것만 구하면 된다.다.(n-1Cr-1)

두번째 경우는 첫번째 숫자가 1이 아닌 경우이므로 첫번째 숫자까지 결정해주어야 한다. (n-1Cr)

이 두개의 경우를 더하면 최종적으로 nCr 이 튀어나온다.

항상 조합을 구하는 식은 저 두가지 경우로 쪼개진다. 그리고 n-1Cr-1을 구하는 두가지 경우는 n-2Cr-1 와 n-2Cr-2 경우로 쪼개질 것이다. 이렇게 최종적으로 쪼갤경우가 없을때까지 nC0 = 1 계속된다.

#include <iostream>
using namespace std;

void print(int *a, int length) {
for (int i = 0; i < length; i++) {
cout << a[i];
}
cout << '\n';
}

void combination(int *a, int index, int n, int r, int target) {
if (r == 0) print(a, index);
else if (target == n + 1) return;
else {
a[index] = target;
combination(a, index + 1, n, r - 1, target + 1);
combination(a, index, n, r, target + 1);
}
}

int main() {
int a[6] = {};

combination(a,0,6,3,1); //6개중에 3개 고르는 조합

return 0;
}

-결과화면-