[Algorithm] 조합 코드 구현 (Java)

완전탐색 알고리즘에서 모든 경우의 수를 계산한 후 결과 값을 찾는 방식이 자주 나온다. 그래서 재귀를 통해 조합을 구현하는 방법에 대해서 정리하려고 한다. 이때 기본 형식은 아래와 같다.

1. 조합(Combination)

조합은 고등학교 수학에서 경우의 수를 계산할 때 순열과 조합 파트로 배웠었다. 프로그래밍에서도 수학에서의 순열과 조합과 같다고 생각하면 된다. 잠시 고등학교 수학에서 배운걸 생각해보면 아래와 같다.

• 순서를 고려하지 않고 선택하는 방법
• nCr : n개 중 r개를 순서에 상관없이 선택하는 방법의 수
• nCr = nPr/r! / (n-r)!r!

간단히 예시를 들면 {1,2,3} 에서 2개를 뽑는 경우의 수 는 3C2로 3X2/2! = 6. 즉, 3가지가 나온다.

{1,2}
{1,3}
{2,3}

arr : 조합을 뽑아낼 배열
visited : 조합에 뽑혔는지 체크하는 배열
n : 배열의 길이
r : 조합의 길이

2. 조합 구현

2.1 백트래킹 이용

start 인덱스를 기준으로 start 보다 작으면 뽑을 후보에서 제외하고, start 보다 크면 뽑을 후보가 됩니다. 그리고 뽑는 개수를 1개부터 n개 까지 반복문을 통해 main메소드에서 호출해주고 있습니다. start는 0부터 시작합니다.

/**
 * 조합 : n 개 중에서 r 개 선택
 */
public class Combination {
    public static void main(String[] args) {
        int n = 4;
        int[] arr = {1, 2, 3, 4};
        boolean[] visited = new boolean[n];

        for (int i = 1; i <= n; i++) {
            System.out.println("\n" + n + " 개 중에서 " + i + " 개 뽑기");
            combination(arr, visited, 0, n, i);
        }
    }

    // 백트래킹 사용
    // 사용 예시 : combination(arr, visited, 0, n, r)
    static void combination(int[] arr, boolean[] visited, int start, int n, int r) {
        if (r == 0) {
            print(arr, visited, n);
            return;
        }

        for (int i = start; i < n; i++) {
            visited[i] = true;
            combination(arr, visited, i + 1, n, r - 1);
            visited[i] = false;
        }
    }

    // 배열 출력
    static void print(int[] arr, boolean[] visited, int n) {
        for (int i = 0; i < n; i++) {
            if (visited[i]) {
                System.out.print(arr[i] + " ");
            }
        }
        System.out.println();
    }
}

2.2 재귀를 이용하여 구현

depth 변수는 현재 인덱스로 생각하시면 됩니다. 현재 인덱스를 뽑는다면 visited[depth] = true, 뽑지 않으면 visited[depth] = false 이렇게 구현하시면 됩니다. 또한 뽑은 경우와 뽑지 않은 경우 모두 호출합니다. 종료하는 경우 조건으로 0개를 뽑을 경우 또는 depth가 n이 되면 모든 인덱스를 다 보았으므로 재귀를 종료합니다.

/**
 * 조합 : n 개 중에서 r 개 선택
 */
public class Combination {
    public static void main(String[] args) {
        int n = 4;
        int[] arr = {1, 2, 3, 4};
        boolean[] visited = new boolean[n];

        for (int i = 1; i <= n; i++) {
            System.out.println("\n" + n + " 개 중에서 " + i + " 개 뽑기");
            comb(arr, visited, 0, n, i);
        }
    }

    // 재귀 사용
    // 사용 예시 : comb(arr, visited, 0, n, r)
    static void comb(int[] arr, boolean[] visited, int depth, int n, int r) {
        if (r == 0) {
            print(arr, visited, n);
            return;
        }
        
        if (depth == n) {
            return;
        }

        visited[depth] = true;
        comb(arr, visited, depth + 1, n, r - 1);

        visited[depth] = false;
        comb(arr, visited, depth + 1, n, r);
    }

    // 배열 출력
    static void print(int[] arr, boolean[] visited, int n) {
        for (int i = 0; i < n; i++) {
            if (visited[i]) {
                System.out.print(arr[i] + " ");
            }
        }
        System.out.println();
    }
}

3. 조합 경우의 수만 셀 경우

public int combination(int n, int r){

    if(n==r || r==0) return 1;
    return combination(n-1, r-1) + combination(n-1,r);

}