중복 조합(Java)

중복 조합

조합은 n개의 숫자 중에서 r개를 뽑아야 할 때 순서를 고려하지 않고 뽑는 것을 말합니다.

오늘 살펴볼 중복 조합은 n개의 숫자 중에 중복을 신경쓰지 않고 r개를 뽑는 것을 뜻합니다.

구현 방법

그렇다면 이 중복 조합은 코드 상에서 어떻게 구현할 수 있을까요?

조합에서는 boolean[] vistied 를 사용해서 선택 여부에 대한 조건을 확인했는데요! 중복 조합은 값이 중복으로 들어가도 괜찮기 때문에 선택 여부를 확인할 필요가 없습니다.

/**
* @param arr 숫자를 뽑아낼 배열
* @param result 뽑은 숫자 결과가 저장될 리스트
* @param start 시작이 될 인덱스 
* @param r 뽑고자 하는 숫자의 개수
*/
static void duplicatedCombination(int[] arr, ArrayList<Integer> result, int start, int r) {
    if(r == 0) {
        print(result);
        return;
    }

    for(int i=start; i<arr.length; i++) {
        result.add(arr[i]);
        duplicatedCombination(arr, result, i, r-1);
        result.remove(result.size()-1);
    }
}

static void print(ArrayList<Integer> result) {
    for(int n: result) {
        System.out.print(n+ " ");
    }

    System.out.println();
}

결과

참고
https://hanyeop.tistory.com/362