[자료구조] 조합

조합 (Combination)이란?

• 순서 없고, 중복 허용하지 않음
• 서로 다른 n개 중에서 r개를 선택하는 경우의 수
• nCr

// 조합
   int n = 4;
   int r = 2;

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

   int fResult = 1;
   for (int i = 1; i <= r; i++) {
       fResult *= i;
   }

   System.out.println(pResult / fResult);

중복 조합

• 순서 없고, 중복 허용한다
• nHr = (n+r-1)Cr
• 중복 조합의 경우, 기본 조합을 계산하는 함수를 만들어 값만 다르게 넣어 해결할 수 있다.

< 해결 할 문제>
1, 2, 3, 4 를 이용하여 세자리 자연수를 만드는 방법 (순서 X, 중복 x)의 각 결과를 출력하시오

순열과 마찬가지로, visited를 이용한 구현을 사용한다. (DFS)
해당 코드는 아래와 같다.

public class Practice {
    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.out.print(arr[i] + " ");
                }
            }
            System.out.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);
    }

    public static void main(String[] args) {
//      Test code
        int[] arr = {1, 2, 3, 4};
        boolean[] visited = {false, false, false, false};

        Practice p = new Practice();
        p.combination(arr, visited, 0, 4, 3);
    }
}

코드만 봐서는 로직이 제대로 이해가 되지 않기 때문에, 직접 값을 넣어보며 진행과정을 살펴보았다.
아래와 같이, depth와 r의 변화에 주의하여 따라가야한다.

또한, 코드에서 r 값이 0일 경우, visited가 true인 값들을 반환하는데, 해당 반환을 끝내고 return에서 어디로 돌아가는지를 잘 확인해야한다.

아래 설명에서는 총 4개 중 2개만 확인하였는데, 그 뒤를 직접 해보길 추천한다!