[완전 탐색] 조합

조합

완전 탐색 중의 한 방법으로 순열과 달리 순서를 상관하지 않는다.

_nC_r로 n개 중에서 r개를 순서 상관없이 고르는 경우의 수이다. r == 0일 때, 1이다.

또한, _nC_r = _n-1C_r + _n-1C_r-1처럼 재귀적 표현이 가능하다.

 

반복문

public class Main {
    public static void main(String[] args) {
        for(int i=0; i<4; i++){
            for(int j=i + 1; j<4; j++){
                for(int k=j + 1; k<4; k++){
                    System.out.println("[" + i + ", " + j + ", " + k + "]");
                }
            }
        }
    }
}

 

재귀함수

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        combination(0, 0);
    }

    static int[] arr = new int[3]; // 조합이 저장되는 배열
    private static void combination(int cnt, int start){
        if(cnt == 3){
            System.out.println(Arrays.toString(arr));
            return;
        }

        for(int i=start; i<4; i++){
            arr[cnt] = i;
            combination(cnt + 1, i + 1); // 중복 조합인 경우 i + 1을 i로 변경하면 된다.
        }
    }
}