[출처] - 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략

문제

0 번부터 차례대로 번호 매겨진 n 개의 원소 중 네 개를 고르는 모든 경우를 출력하는 코드를 작성해 보자.

풀이

1. 중첩 반복문

void combination_iter(int n, int r) {
	
	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;
				}

	return;

}

중첩 반복문으로 쉽게 이 문제를 해결할 수 있다. 하지만 조합의 r 값은 전혀 사용되어지지 않으며, 만약 원소를 고르는 개수가 네 개가 아닌 다섯개, 여섯개라면 추가되는 원소수에 맞게 중첩문을 추가해야 한다는 문제점이 있다.

2. dfs 를 활용한 재귀문

void combination_rec(int n, vector<int>& picked, int r) {
	if(r == 0) {
		printPicked(picked);
		return;
	}

	int smallest = picked.empty() ? 0 : picked.back() + 1;

	for(int i = smallest; i < n; i++) {
		picked.push_back(i);
		combination_rec(n, picked, r-1);
		picked.pop_back();
	}

}

void printPicked(vector<int>& picked) {
	for(int i = 0; i < picked.size(); i++)
		cout << picked[i];

	cout << endl;

}

재귀문을 활용한다면, 앞선 문제점을 해소할 수 있다.

동작은 다음과 같다.

root 에서 시작되어 for 문 내에서 재귀가 이뤄진다.

int smallest = picked.empty() ? 0 : picked.back() + 1;

for(int i = smallest; i < n; i++) {
	//...
    }

기본적으로 중복되는 숫자가 없도록 오름차순의 순서를 유지하기 위하여, smallest 변수를 활용한다.
이를 활용하여, 호출된 함수에 for 문을 이를 호출한 함수에 i 값 보다 +1 이 된 값에서 시작되도록 구현하였다.

이 때, 처음 시작이 되는 root 에선 호출한 함수의 값을 받아올 수 없기 때문에, 삼항 연산자를 통하여 0 의 값을 대입해 주었다.

picked.push_back(i);
combination_rec(n, picked, r-1);
picked.pop_back();

재귀가 종료되고 이전 스택으로 돌아갈 때에는 다시 리스트에 pop 을 해주어 이전 스택의 리스트를 유지한다.

if(r == 0) {
	printPicked(picked);
	return;
}

만약 picked 리스트에 원소들의 수가 r 의 값과 같아진다면, 이를 출력한다.