[Algorithm] n개의 원소중 m개를 고르는 모든 경우 찾기(C++)

0번부터 차례대로 번호 매겨진 n개의 원소 중 4개를 고르는 모든 경우를 출력하는 코드를 생각해봅시다.

 

만약 n = 6인경우 출력은 다음과 같습니다.

(0, 1, 2, 3)
(0, 1, 2, 4)
(0, 1, 2, 5)
... 중략 ...
(2, 3, 4, 5)

위 출력은 다음과 같은 4중 for문으로 간단하게(?) 해결할  수 있습니다.

 

for(int i = 0; i < n; ++i)
	for(int j = i+1; j < n; ++j)
		for(int k = j+1; k < n; ++k)
			for(int l = k+1; l < n; ++l)
				cout << i << " " << j << " " << k << " " << l << endl;

 

하지만 원소의 수가 늘어날 수록 코드가 길고 복잡해지며, 만약 골라야할 원소의 수가 유동적이라면 사용할 수 없다는 문제가 있습니다.

 

따라서 다음과 같이 재귀함수로 위 문제를 해결할 수 있습니다. 

// n : 전체 원소의 수
// picked : 지금까지 고른 원소들의 번호
// toPick : 더 골라야할 원소의 수

void pick(int n, vector<int>& picked, int toPick){
	// 더 고를 원소가 없는 경우 원소들을 출력
	if(toPick == 0){
		printPicked(picked);
		return;
	}
    
	// 고를 수 있는 가장 작은 번호 계산
	int smallest = picked.empty() ? 0 : picked.back() + 1;
    
	// 원소를 하나 골라서 재귀함수 호출
	for(int next = smallest; next < n; ++next){
		picked.push_back(next);
		pick(n, picked, toPick-1)
		picked.pop_back();
	}
}

 

골라야할 원소가 유동적이거나, 개수가 많은 경우 모두 위의 코드로 해결할 수 있습니다.

 

위와 같이 재귀 함수를 이용하면 특정 조건을 만족하는 조합을 모두 생성하는 코드를 쉽게 작성할 수 있습니다. 

따라서 재귀 함수는 완전 탐색을 구현할 때 아주 유용합니다.