[Java] 조합 알고리즘 java 코드로 구현하기

조합이란?

배열에서 몇개를 중복없이 추출하는 것을 말한다.

 

예를 들면, 배열 int[] arr = {1, 2, 3, 4} 에서 2개의 요소만 중복없이 추출하고 싶은 경우

[1, 2], [2, 3], [3, 4]

[1, 3], [2, 4]

[1, 4]

 

총 6개가 출력되어야 한다.

 

조합을 구현할때 백트래킹과 재귀함수 방법이 있다고 한다.

 

나는 너무 헷갈려서 우선 가장 간단한 예제로 조합을 구현해보았고, 나중에 프로그래머스에서 문제 풀 때 조건만 다르게 해서 적용해 볼 예정이다.

 

코드

class CombinationExample {

    public static void main(String[] args) {
        int[] arr = {1,2,3,4};
        getCombination(arr);
    }

    public static void getCombination(int[] arr) {
        comb(arr, new int[2], 0, 0);
    }

    public static void comb(int[] arr, int[] selectArr, int startIdx, int pickCnt) {
        if (pickCnt == 2) {
            System.out.println("[" + selectArr[0] + ", " + selectArr[1] + "]");
            return;
        }
        for (int i = startIdx; i < arr.length; i++) {
            selectArr[pickCnt] = arr[i];
            // 가지치기 부분
            // 주의: startIdx 부분에 startIdx + 1 이라고 넣었더니 결과가 이상하게 나와서 한참 헤맸음.
            comb(arr, selectArr, i + 1, pickCnt + 1);
        }
    }
}

 

출력결과

 

 

comb() 함수의 파라미터

- 원래 기준이 되는 배열 arr

- 뽑힌 수만 넣은 배열 selectArr

- for문 돌때 기준점이 되는 startIdx

- 뽑은 갯수(selectArr의 idx로도 사용가능) pickCnt

 

 

※ 다른 블로그들의 조합 코드를 보면 boolean[] 배열로 visited 여부를 나타낸 코드가 많은데, for문 돌때 i = startIdx 이기 때문에 visited 배열이 없어도 방문했던 idx는 방문하지 않게됨