c++ 재귀 알고리즘을 이용한 조합(combination) 생성

이전에 포스팅한 재귀 알고리즘을 이용한 부분 집합 생성 알고리즘과 유사한 방식이다.

 

참고: 재귀함수를 이용한 부분 집합 생성 알고리즘

재귀 함수를 이용한 부분 집합 생성 알고리즘

---

아래는 n = 7 , r = 4 라고 가정하고 7C4의 경우를 모두 출력하는 코드이다.

#include <iostream>
#include <vector>
using namespace std;

vector<int> comb;
int n = 7, r =4;

void combination(int k) {
	if (comb.size() == r) {
		for (int i = 0; i < comb.size(); i++)
			cout << comb[i] << " "; cout << endl;
	}
	else if( k == n + 1 ){

	}
	else {
		comb.push_back(k);
		combination(k + 1);
		comb.pop_back();
		combination(k + 1);
	}
}

int main() {
	combination(1);

	return 0;
}

 

 

실행 결과 : 

---

짧은 코드로 쉽게 구현할 수 있지만, 재귀 함수를 이용하다보니 재귀 알고리즘에 익숙하지 않다면 한 눈에 동작을 이해하기 어려울 것 같다. 

 

k에 인자 1을 넣고 함수를 실행하고 벡터 안에 r개의 원소가 다 차거나,  k가 n보다 커지면 재귀 스택이 종료된다.

 

한번 직접 코드를 입력한 후에 n과 r을 낮은 값으로 넣고 직접 실행해보는 것을 추천한다.