[알고리즘] [7] 조합

1. 조합 (Combination)

• 서로 다른 n개의 원소 중 r개를 순서 없이 택하는 것
• nCr = n-1Cr-1 + n-1Cr 의 재귀적 표현이 가능하다.
• nC0 = 1

재귀를 이용한 조합 생성

// nCr

input[]; // n 개의 원소를 가지는 배열
numbers[]; // 조합을 저장할 r 크기의 배열

comb(cnt, start) { // cnt : 현재까지 선택한 원소 개수. start : 조합할 원소의 시작 인덱스
	if (cnt == r) {
    	return;
    }
    else {
    	for (i = start; i < n; i++) {
        	numbers[cnt] = input[i];
            comb(cnt + 1, i + 1);
        }
    }
}

---

2. 중복조합

• 순서가 무관하지만 원소의 중복이 가능한경우
• nHr = n+r-1Cr

// nHr

input[]; // n 개의 원소를 가지는 배열
numbers[]; // 조합을 저장할 r 크기의 배열

comb(cnt, start) { // cnt : 현재까지 선택한 원소 개수. start : 조합할 원소의 시작 인덱스
	if (cnt == r) {
    	return;
    }
    else {
    	for (i = start; i < n; i++) {
        	numbers[cnt] = input[i];
            comb(cnt + 1, i); // 현재 인덱스부터 선택
        }
    }
}