조합

n개의 숫자 중에서 r개의 수를 순서 없이 뽑는 경우
예를 들어 [1, 2, 3] 이란 숫자 배열에서 2개의 수를 순서 없이 뽑으면

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

이다.

공식

nCr =n−1Cr−1+n−1Cr

• 하나의 원소를 이미 선택하고, 나머지 원소들에서 남은 것을 선택하는 경우의 수 + 하나의 원소를 선택하지 않고 나머지 원소들에서 선택하는 경우의 수

이런 성질을 이용해 조합을 코드로 구현하자.

조합 경우의 수 구하기

먼저, nCr 에서 r==n 이거나 r==0일 때 경우의 수는 1이다.

이 성질을 이용해보자.

public class combination {

    public static int comb(int[] arr, int n, int r) {
        if(n ==r || r == 0) {
            return 1;
        } else {
            return comb(arr, n-1, r-1) + comb(arr, n-1, r);
        }
    }

    public static void main(String[] args) {
        int[] arr = {1,2,3};
        comb(arr, 3, 2);
    }
}

조합 출력하기

경우의 수가 아닌, 조합의 원소를 직접 사용해야 할때가 있다.

• 재귀적으로 구현한다.

• 원소를 하나씩 돌면서, 해당 원소를 선택하고 나머지 중 r-1개를 찾는 경우와 해당 원소를 선택하지않고 나머지 중 r개를 찾는 경우를 재귀로 구현한다.

• 출력되는 조건은 뽑을 것이 더이상 없을 때 (r==0)이다.
  -> 이때 visited가 true인 것을 출력한다.

• visited는 해당원소가 선택되었는지 체크한다.

• idx가 arr.length와 같으면 더이상 원소가 없기때문에 종료한다.

public class combinationValue {
    public static void comb(int[] arr, boolean[] visited, int index, int r) {
        if(r == 0) {
            for(int i=0; i< visited.length; i++) {
                if(visited[i]) {
                    System.out.print(arr[i] + " ");
                }
            }
            return;
        }

        if(index == arr.length) {
            return;
        } else {
            visited[index] = true;
            comb(arr, visited, index+1, r-1);

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

    public static void main(String[] args) {
        int[] arr = {1,2,3};
        boolean[] visited = new boolean[arr.length];

        int r= 2; // 몇개 뽑을건지
        comb(arr, visited, 0, r);
    }
}

시간복잡도

모든 조합의 합은 이항계수의 성질에 따라 한번 재귀호출시마다 2개의 함수를 호출하기 때문에 시간복잡도는 O(2^n)을 가집니다.

O(2^N)

---

참고
https://youngssse.tistory.com/entry/Algorithm-JAVA%EC%97%90%EC%84%9C-%EC%A1%B0%ED%95%A9-Combination