조합 (Combination)

조합 (Combination)

• 서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것
• 서로 다른 n개 중 r개를 택하는 조합의 경우의 수는 아래와 같다.

 

소스코드

import java.util.Arrays;

public class Combination {
    public static void combination(int[] arr, int n, int r, int depth, int idx) {
        if (depth == r) {
            System.out.println(Arrays.toString(arr));
            return;
        }

        for (int i = idx; i < n; i++) {
            arr[depth] = i;
            combination(arr, n, r, depth + 1, i + 1);
        }
    }

    public static void main(String[] args) {
        combination(new int[2], 4, 2, 0, 0);
    }
}

실행결과

 

여기서 point !

- depth 는 몇번째 선택인 지를 나타내는 변수

- idx는 앞에 선택한 것을 제외해주어야하기 때문에 그 depth에서 선택가능한 것을 구해주는 변수

- return문이 있는 종료조건에 원하는 코드를 짜면 된다.

 

예시)

Arrays.toString(arr) 가 호출되는 경우만 그렸습니다.