재귀를 활용한 조합의 구현

백준 15650번 문제(N과 M(1))를 해결한 코드입니다.

코드

import java.util.Scanner;

public class P15650 {
	static int n, r;
	static int[] arr;
	static StringBuilder sb;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		r = sc.nextInt();

		arr = new int[r];
		sb = new StringBuilder();
		combination(0, 0);
		System.out.println(sb);
	}

	static void combination(int ind, int depth, int visited) {
		if (depth == r) {
			for (int i = 0; i < r; i++) {
				sb.append(arr[i]+1).append(" ");
			}
			sb.append("\n");
			return;
		}

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

상세 설명

nCr을 구현하였다.

main 메서드
arr은 조합으로 얻어진 r개의 숫자를 담을 배열이다. combination 메서드를 통해 재귀적으로 arr에 들어갈 원소를 구해나갈 것이다.

combination 메서드
depth가 r과 같아지면 기저조건에 도착하여 수행해야 할 코드 블럭을 수행한다. 아직 도달하지 못했을 경우, 반복과 재귀를 이용하여 r개를 뽑아나가야 한다.

만일 5개의 원소 중 3개를 선택한다고 할 때, 반복문을 이용하면 다음과 같이 나타낼 수 있다.

for(int i1=0; i1<3; i1++) {
	// i1 선택
	for(int i2=i1+1; i2<4; i2++) {
		// i2 선택
	   	for(int i3=i2+1; i3<5; i3++) {
	   		// i3 선택
	       	System.out.printf("%d %d %d\n", i1, i2, i3);
	    }
	}
}

이를 일반화하여 n개의 원소중 r개를 선택한다고 해볼 때, 다음과 같이 r중 for문을 이용하여 코드를 작성할 수 있다.

for(int i_1 = 0; i_1 < n-r+1; i_1++){
	for(int i_2 = i_1+1; i_2 < n-r+2; i_2++){
    	for(int i_3 = i2+1; i_3 < n-r+3; i_3++){
            ...
               	for(int i_r_1 = i_r_2 + 1; i_r_1 < n-1; i_r_1++){
                   	for(int i_r = i_r_1 + 1; i_r < n; i_r++){
                       	~~~
                    }
                }
            ...
        }
    }
}

적은 숫자만큼 뽑을 때에는 for문만으로 가능하지만, 임의의 r개를 뽑기 위해서는 재귀를 이용해야 한다.

for(int i = ind; i <= n - r + depth; i++) {
	// 결과가 될 arr에 담기
	combination(i+1, depth+1);
}