[알고리즘] 조합(Combination)

조합(Combination)

개념

- 서로 다른 것들(n개) 중에서 몇 개(r개)를 순서없이 골라낸 것

- nCr

- 순서가 의미가 있으면 순열 / 순서가 의미가 없으면 조합

 

구현

- 중복체크를 안하면서 코드가 더 간결해짐

- 시작 위치(start)를 매개변수로 넘겨 매개변수부터 끝까지 탐색 -> 중복이 발생하지 않음

- 현재 뽑은 수가 i이므로 i 다음 수부터 조합을 시도하도록 i+1을 넘김

- input[] : 서로 다른 숫자(n개)를 저장하기 위한 Integer 배열

- numbers[] : 뽑은 숫자(r개)를 저장하기 위한 Integer 배열

 

코드

public static void combination(int cnt, int start){
        if(cnt == R){
            System.out.println(Arrays.toString(numbers));
            return;
        }

        for(int i = start; i<N; i++){
            numbers[cnt] = input[i];
            combination(cnt+1, i+1);
        }
}