[알고리즘] 조합 ex) 5개 중 3개 뽑는 방법

오늘 모 기업 코딩테스트를 봤는데 조합 문제가 나와서 올려본다.

 

예: 5개의 숫자 중 3가지를 뽑는 방법... 중복 없이!

 

    public class Main {
    static void combination(int[] arr, boolean[] visited, int start, int n, int r) {
        if (r == 0) {
            for (int i = 0; i < arr.length; i++) {
                if (visited[i]) System.out.print(arr[i] + " ");
            }
            System.out.println("");
            return;
        }
        for (int i = start; i < n; i++) {
            visited[i] = true;
            combination(arr, visited, i + 1, n, r - 1);
            visited[i] = false;
        }

    }

    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5};
        boolean[] visited = new boolean[array.length];
        combination(array, visited, 0, array.length, 3);
    }
}

실행 시

 

재귀를 이용해 해결했다.

앞에서 부터 순서대로 뽑는 과정

 

 

처음에 3개를 뽑고 r이 0이되면 return을 해준다.

재귀를 사용했기 때문에 Stack에 넣었다가 빼는 것과 같이 i = 2로 돌아가 visited[2] = false 로 만들고 다음으로(i=3) 넘어간다.

 

 

이렇게 순차적으로 앞에서부터 3개를 뽑아 출력해준다.