[Java] 조합 (Combination)

• 순열과 조합의 차이

    뽑힌 자리 (순서의 의미 X )→ 조합 
    뽑힌 자리 (순서의 의미 0 )→ 순열

💡 조합

nCr

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class CombinationTest {

    static int N, R;
    static int totalCnt;
    static int[] arr, input;

    // nCr: n까지의 수 중 r개를 모두 뽑아서 순서있게 나열함(1<r<n)

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());

        totalCnt = 0;
        input = new int[N];
        arr = new int[R];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            input[i] = Integer.parseInt(st.nextToken());

        }

        com(0, 0);
        System.out.println("총 경우의 수 :" + totalCnt);
    }

    // cnt+1번째 해당하는 조합에서 포함될 수를 뽑기
    private static void com(int cnt, int start) {

        if (cnt == R) {
            totalCnt++;
            System.out.println(Arrays.toString(arr));
            return;
        }

        // 가능한 모든 수에 대해서 탐색 ->(input 배열의 모든 수를 시도해야함 )
        // start 부터 처리시 중복 수 추출 방지 및 순서가 다른 조합 추출을 방지함
        for (int i = start; i < N; i++) {
            // start 부터 처리 -> 중복체크가 필요 없어짐!
            arr[cnt] = input[i];
            // 다음 수 뽑으러
            com(cnt + 1, i + 1);
        }

    }
}