[Java] 조합 Combination 구현하기!

참고한 블로그⬇️

조합 Combination (Java)

 

조합 : n개의 숫자 중에서 r개의 수를 순서 없이 뽑는 경우

e.g. [1, 2, 3] 배열 중 2개의 수를 순서 없이 뽑는 경우

[1, 2], [1, 3], [2, 3]

 

 

핵심 내용

• 배열을 처음부터 끝까지 돌며
  • 현재 인덱스를 선택하는 경우
  • 현재 인덱스를 선택하지 않는 경우
• 두 가지로 모든 경우를 완전탐색할 것

변수	설명
arr	조합을 뽑아낼 배열
output	조합에 뽑혔는지 체크하는 배열
n	배열의 길이
r	조합의 길이

 

순열과 달리 조합은 r을 유지할 필요가 없으므로 숫자를 하나 뽑을 때마다 r을 하나씩 줄여줘야 한다.

r == 0일 때, r개의 숫자를 뽑았다고 본다.

 

 

백트래킹

start 변수 = 기준

start 인덱스를 기준으로 start보다 작으면 뽑을 후보에서 제외, start보다 크면 뽑을 후보가 된다.

 

예를 들어 [1, 2, 3] 배열이 있고 start가 0부터 시작이라고 해보자.

함수에 들어오면 먼저 i가 start부터 시작하는 for문에 들어간다.

만약 0 인덱스인 1을 뽑는다면 visited[0] = true가 되고, 뽑지 않는다면 visited[0] = false이다.

 

1을 선택한 경우와, 그렇지 않은 경우 둘 다를 봐야한다.

하지만 더이상 1은 고려 대상이 아니기 때문에 다음 for문은 무조건 i + 1부터 시작한다.

 

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;
    }
}

 

 

재귀

depth 변수 = 현재 인덱스

현재 인덱스를 뽑는다면 visited[depth] = true, 아니라면 visited[depth] = false

마찬가지로 뽑은 경우와 뽑지 않은 경우 모두 봐야하고, 이전에 본 값들은 더이상 고려 대상이 아니기 때문에 depth는 1씩 증가해야 한다.

depth == n이 되면 모든 인덱스를 다 보았으니 재귀 종료한다.

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);
}

 

둘의 성능차이는 없다.