[JM북][완전탐색] n개의 원소 중 m개를 고르는 모든 조합을 찾는 알고리즘

n개의 원소 중 m개를 고르는 모든 조합을 찾는 알고리즘을 재귀함수를 이용해서 풀면 소스코드는 다음과 같다.

- 소스코드

import java.util.ArrayList;

public class Main {
	
	//n : 전체 원소의 수
	//picked : 지금까지 고른 원소들의 번호
	//toPick : 더 고를 원소의 수
	//일 때, 앞으로 toPick개의 원소를 고르는 모든 방법을 출력한다.
	static void pick(int n, ArrayList<Integer> picked, int toPick){
		//기저 사례 : 더 고를 원소가 없을 때 고른 원소들을 출력한다.
		if(toPick == 0){
			System.out.println(picked);
			return;
		}
		
		//고를 수 있는 가장 작은 번호를 계산한다.
		int smallest = picked.isEmpty() ? 0 : picked.get(picked.size() - 1) + 1;
		
		for(int next = smallest; next < n; next++){
			picked.add(next);
			pick(n, new ArrayList<Integer>(picked), toPick - 1);
			picked.remove(picked.size() - 1);
		}
	}
	
	public static void main(String[] args) {
		ArrayList<Integer> arr = new ArrayList<Integer>();
		pick(5, arr, 2); // n, arraylist, m
	}
}

- Category : Brute-Force(완전탐색)

- My Thiking : 그래프 탐색 알고리즘이나 트리의 순회를 재귀함수로 구현했을 때의 유사한 방식이라고 생각했다. 평소에 재귀함수에 대해 약했기 때문에 이러한 알고리즘들을 많이 공부해야 한다고 생각했다.

 

- Logic : 이 코드는 텅 빈 답에서 시작해서 매 단계마다 하나의 원소를 추가하는 일을 반복하다가, 하나의 답을 만든 뒤에는 이전으로 돌아가 다른 원소를 추가하는 식으로 모든 답을 생선한다.

여기서 재귀함수를 사용한 이유는 만약 반복문을 사용한다면 m개의 갯수만큼 반복문이 늘어나기 때문에 코드가 길고 복잡해지는데다, 골라야할 원소의 수가 입력에 따라 달라질 수 있는 경우에는 사용할 수 없다는 문제가 있다.