조합 (Combination)

조합

조합은 서로 다른 n개에서 순서 없이 r개의 숫자를 뽑는 경우의 수를 의미한다.

static int K;
static int[] arr;
static boolean[] visited;

// 조합
public static void main(String[] args) {
    arr = new int[]{1, 2, 3};
    K = 2;   // 뽑는 개수
    visited = new boolean[arr.length];   //배열의 개수만큼 초기화
    combination(0, 0);
}

public static void combination(int idx, int cnt) {
    if (cnt == K) {
        for(int i = 0; i < arr.length; i++) {
            if(visited[i]) System.out.print(arr[i]);
        }
        System.out.println();
        return;
    }
    for (int i = idx; i < arr.length; i++) {
        if (!visited[i]) {
            visited[i] = true;
            combination(i + 1, cnt + 1);
            visited[i] = false;
        }
    }
}

/* 출력
12
13
23
 */

중복 조합

중복 조합은 서로 다른 n개에서 순서 없이 중복이 가능하게 r개의 숫자를 뽑는 경우의 수를 의미한다.

static int K;
static int[] arr, result;

// 조합
public static void main(String[] args) {
    arr = new int[]{1, 2, 3};
    K = 2;   // 뽑는 개수
    result = new int[K];
    combination(0, 0);
}

public static void combination(int idx, int cnt) {
    if (cnt == K) {
        for(int num : result){
            System.out.print(num);
        }
        System.out.println();
        return;
    }
    for (int i = idx; i < arr.length; i++) {
        result[cnt] = arr[i];
        combination(i, cnt + 1);
    }
}

/* 출력
11
12
13
22
23
33
 */