조합(Combination)은 주어진 집합에서 일부 원소를 선택하여 순서에 상관없이 나열하는 방법을 의미합니다. 주어진 집합의 원소들 중에서 일부를 선택하여 조합을 만들 때, 선택된 원소들의 순서는 고려되지 않습니다.

$_{n}C_r\ =\ \frac{n!}{(n-r)!r!}\ =\ \frac{_{n}P_r}{r!}$ (단, 0 < r ≤ n)

중복 조합

• 서로 다른 n개 중에서 r개를 선택하는 경우의 수 (순서X, 중복O)
  • 예시) 후보 2명, 유권자 3명일 때 무기명 투표 방법

$_{n}H_r\ =\ _{n+r-1}C_r$

조합 코드 예시

public class Main {

    static int getCombination(int n, int r) {
        int pResult = 1;
        for (int i = n; i >= n - r + 1; i--) {
            pResult *= i;
        }

        int rResult = 1;
        for (int i = 1; i <= r; i++) {
            rResult *= i;
        }

        return pResult / rResult;
    }

    public static void main(String[] args) {
//      1. 조합
        System.out.println("== 조합 ==");
        // 서로 다른 4명 중 주번 2명 뽑는 경우의 수
        int n = 4;
        int r = 2;

        int pResult = 1;
        for (int i = n; i >= n - r + 1; i--) {
            pResult *= i;
        }

        int rResult = 1;
        for (int i = 1; i <= r; i++) {
            rResult *= i;
        }
        System.out.println("결과 : " + pResult / rResult);

//      2. 중복 조합
        System.out.println("== 중복 조합 ==");
        // 후보 2명, 유권자 3명일 때 무기명 투표 경우의 수
        n = 2;
        r = 3;

        System.out.println("결과 : " + getCombination(n + r - 1, r));

    }
}

// 1, 2, 3, 4 를 이용하여 세자리 자연수를 만드는 방법 (순서 X, 중복 x)의 각 결과를 출력하시오

public class Practice {
    void combination(int[] arr, boolean[] visited, int depth, int n, int r) {
        if (r == 0) {
            for (int i = 0; i < n; i++) {
                if (visited[i]) {
                    System.out.print(arr[i] + " ");
                }
            }
            System.out.println();
            return;
        }

        if (depth == n) {
            return;
        }
        
        visited[depth] = true;
        combination(arr, visited, depth + 1, n, r - 1);

        visited[depth] = false;
        combination(arr, visited, depth + 1, n, r);
    }

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

        Practice p = new Practice();
        p.combination(arr, visited, 0, 4, 3);
    }
}