[Java]중복 조합(Combination with Repetition)

중복 조합은 조합과 비슷하게 n개의 요소 중 r개를 순서에 상관없이 뽑는데,

 

중복을 허용하여 뽑는 경우의 수이다.

 

유도 과정은 생략하고, 실제로 어떻게 동작하는지는 아래 그림을 보면 쉽다.

 

5개의 요소 중 중복 조합으로 2개를 뽑는 경우의 수를 나타내고 있다.

 

중복 순열을 구현할 때와 비슷하게 isVisited 배열을 제거하고,

 

재귀 함수를 호출할 때 i + 1이 아닌 i부터 대입해 중복을 허용하면 된다.

public class CombinationWithRepetition {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5}; // 중복 조합을 만들 배열
        int n = arr.length;
        int r = 2;
        comb(arr, new int[r], 0, 0, n, r); // n개중 r개를 중복 조합으로 뽑는 경우 출력

    }

    static void comb(int[] arr, int[] output, int start, int depth, int n, int r) {

        if(depth == r) {
            for(int i = 0; i < output.length; i++) {
                System.out.print(output[i]);
            }
            System.out.println();
            return;
        }
        for(int i = start; i < n; i++)  {
             // 재귀함수 호출
            output[depth] = arr[i];
            comb(arr, output, i, depth + 1, n, r); // i + 1이 아닌 i 대입, r - 1이 아닌 r 대입
        }
    }
}

// 출력 결과
11
12
13
14
15
22
23
24
25
33
34
35
44
45
55

위 그림과 같은 결과를 얻는 것을 알 수 있다.