조합(Java)

조합

조합은 n개의 숫자 중에서 r개를 뽑아야 할 때 순서를 고려하지 않고 뽑는 것을 말합니다.

구현 방법

그렇다면 이 조합은 코드 상에서 어떻게 구현할 수 있을까요?

가장 중요한 포인트는 해당 인덱스의 숫자를 선택하냐, 안하냐의 두 가지가 경우가 존재한다는 것입니다!

백트래킹

백트래킹을 사용해서 조합을 구현할 때에는 start 변수를 사용합니다.

start 변수는 인덱스를 표현하는데요. arr[start]의 값을 선택하든지, 선택하지 않든지 두 가지 경우가 생기게 됩니다.

선택하면 visited[start] = true 가 되고 선택하지 않으면 visited[start] = false가 되며 선택한 경우에는 start를 +1 증가시켜서 다음 숫자를 고르면 됩니다.

/**
* @param arr 숫자를 뽑아낼 배열
* @param visited 선택 여부를 체크할 배열
* @param start 시작 기준 인덱스
* @param n 기준 배열의 크기
* @param r 뽑고자 하는 숫자의 개수
*/
static void combination(int[] arr, boolean[] visited, int start, int n, int r) {
        if(r == 0) {
            print(arr, visited);
            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) {
    for(int i=0; i<visited.length; i++) {
        if(visited[i]) System.out.print(arr[i] + " ");
    }

    System.out.println();
}

재귀

/**
* @param arr 숫자를 뽑아낼 배열
* @param visited 선택 여부를 체크할 배열
* @param depth 현재 진행 중인 깊이
* @param n 기준 배열의 크기
* @param r 뽑고자 하는 숫자의 개수
*/
static void combination(int[] arr, boolean[] visited, int depth, int n, int r) {
        if(r == 0) {
            print(arr, visited);
            return;
        }

        if(depth == n) return;
        
        visited[depth] = true;
        combination(arr, visited, depth+1, n, r-1); // arr[depth]를 선택하는 경우

        visited[depth] = false;
        combination(arr, visited, depth+1, n, r); // arr[depth]를 선택하지 않는 경우
    }

static void print(int[] arr, boolean[] visited) {
    for(int i=0; i<visited.length; i++) {
        if(visited[i]) System.out.print(arr[i] + " ");
    }

    System.out.println();
}

결과

백트래킹과 재귀 모두 해당 인덱스의 숫자를 선택하냐, 안하냐의 두 가지가 경우가 존재한다는 것이 가장 중요한 개념입니다!

참고
https://bcp0109.tistory.com/15