재귀함수를 사용해 n개의 원소 중 m개를 고르는 모든 조합 찾기

종만북 brute force 챕터에 있는 코드입니다.

 

n개의 원소 중 네개를 고르려면? 4중 for문을 쓰면 됩니다. 하지만 개수가 더 많아지면 코드도 길어지고 복잡해집니다. 고르는 개수가 변경될 때 유연하게 대처할 수도 없고요.

조합을 만들 때 재귀함수를 사용하면 간결하게 코드를 작성할 수 있습니다.

 

void printPicked(vector<int>& picked) {
	for (auto& v : picked)
		cout << v << ' ';
	cout << '\n';
}

// n: 전체 원소의 수
// picked: 지금까지 고른 원소들의 번호(인덱스)
// toPick: 더 고를 원소의 수
// 일 때, 앞으로 toPick개의 원소를 고르는 모든 방법을 출력
void pick(int n, vector<int> &picked, int toPick) {
	// base case: 더 고를 원소가 없을 때 고른 원소들을 출력
	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();
	}
}

 

5개 중 3개를 고르는 모든 조합을 구하겠다고 하면

vector<int> v;
pick(5, v, 3);

이런식으로 쓰면 됩니다.