조합 이란?

서로 다른 n개의 원소 중 r개를 순서와 상관없이 선택하는 것을 조합이라 한다. nCr로 그 경우의 수를 나타낸다.

combination.png

단순 조합 제작

for 중첩으로 조합을 생성한다. 순열은 데이터를 나열한다면, 조합은 데이터의 선택 여부가 중요하다.

그래서 첫 for에서 모든 원소를 후보로 삼을 수 없다.

// 5C3
 int n = 5;
// i 는 0 부터 n - 2 까지 반복해야 안쪽 반복문에서 선택할 요소가 남는다.
for (int i = 0; i < n - 2; i++) {
    // j 는 i + 1 부터 n - 1 까지
    for (int j = i + 1; j < n - 1; j++) {
        // k 는 j + 1 부터 n 까지
        for (int k = j + 1; k < n; k++) {
            // 마지막 순간의 i, j, k 는 n - 2, n - 1, n이 된다.
            System.out.printf("%d %d %d%n", i, j, k);
        }
    }
}

재귀 함수로 조합 생성

for 중첩 대신 재귀함수를 사용하며, 선택의 여부를 배열로 저장한다.

private void combNumbers(
        int n, int r,
        // 몇번째 원소를 고르고 있는지
        int k,
        // 어떤 숫자를 판단하고 있는지
        int next,
        // 현재 완성한 조합
        int[] comb
) {
    // k == r: 고를 만큼 원소를 골랐다
    if (k == r) {
        System.out.println(Arrays.toString(comb));
    }
    // next == n: 고르기 전 고를 대상이 떨어졌다
    else if(next == n) {
        return;
    }
    else {
        // comb[k]에 이번에 판단중인 숫자를 우선 할당한다.
        comb[k] = next;
        // next를 선택하고, k + 1번째 원소를 판단하러 넘어간다.
        combNumbers(n, r, k + 1, next + 1, comb);
        // next를 선택하지 않고 k번째 원소를 판단하러 넘어간다.
        // next를 선택하지 않으면 comb[k]에 할당한 next는 덮어씌워진다.
        combNumbers(n, r, k, next + 1, comb);
    }
}

<aside> 📌

출처. 테킷_알고리즘 4주차_README

</aside>