[자료구조] 조합 (Combination)

1. 조합

• 서로 다른 n개 중에서 r개를 선택하는 경우의 수 (순서 X, 중복 X)
• nCr = n! / (n - r)!r! = nPr / r! (단, 0 < r ≤ n)

2. 중복 조합

• 서로 다른 n개 중에서 r개를 선택하는 경우의 수 (순서 X, 중복 O)
• nHr = (n+r-1)Cr

3. 코드

private static int getComb(int n, int r) {
    int pResult = 1;
    int rResult = 1;

    // nPr
    for (int i = n; i >= n-r+1; i--) {
        pResult *= i;
    }

    // r!
    for (int i = 1; i <= r; i++) {
        rResult *= i;
    }

    return pResult / rResult;
}

// 1. 조합
// 서로 다른 4명 중 주번 2명을 뽑는 경우의 수
int n = 4;
int r = 2;

getComb(n, r); // 6

// 2. 중복 조합
// 후보 2명, 유권자 3명일 때 무기명 투표하는 경우의 수
n = 2;
r = 3;

getComb(n+r-1, r); // 4

// 조합 구현
private static void combination(int[] arr, boolean[] visited, int depth, int n, int r) {
	if(r == 0) {
    	for (int i = 0; i < n; i++) {
        	if (visited[i]) {
            	System.our.print(arr[i] + " ");
            }
        }
        System.our.println();
        return;
    }
    
    if(depth == n) {
    	return;
    }
    
    visited[depth] = true;
    combination(arr, visited, depth+1, n, r-1);
    visited[depth] = false;
    combination(arr, visited, depth+1, n, r);
}