[백준 6603번] 재귀를 통한 조합 구현

문제 링크: 6603번 로또

https://www.acmicpc.net/problem/6603

 

자료구조 시간에 순열을 재귀로 구현하는 것을 배울 때, 조합은 어떻게 할 수 있을지 고민했었던 기억이 있다. 아이디어 자체는 비슷하다. 순열에서 원래의 배열대로, 그리고 swap한 배열대로 출력하는 것처럼 조합도 마찬가지로 어떤 원소가 포함된 것, 그리고 그렇지 않은 것으로 나누면 생각하기가 쉽다. Python으로 구현하면 mutability 때문에 조금 귀찮아질 것 같아서 C++로 구현했다.

 

#include <iostream>
#include <vector>
#define LOTTO_TARGET_SIZE 6

using namespace std;

void comb(vector<int> &arr, vector<vector<int>> &combs, vector<int> cur, int start, int targetSize, int &n) {
	/*
		arr: 처음에 입력받은, k(k>=6)개 조합 벡터
		combs: 완성 조합 벡터들을 저장하는 벡터
		cur: 현재까지 선택한 미완성 조합 벡터
		start: 아직 뽑지 않은 숫자의 시작 인덱스
		targetSize: 뽑아야 하는 남은 숫자 개수
		n: 뽑아야 하는 총 숫자 개수

		한 개의 숫자를 뽑는 경우, 뽑지 않는 경우로 나누어서
		남은 숫자들에 대해 뽑아야 하는 남은 숫자 개수만큼 뽑는다.

		targetSize가 0이 되면 combs에 cur를 추가하고 return한다.
		targetSize가 0이 되지 않았더라도 start가 arr의 마지막 인덱스를 넘으면 return한다.
	*/
	if (targetSize == 0) {
		combs.push_back(cur);
		return;
	}
	if (start == n)
		return;

	// arr[start]를 포함하는 경우
	cur.push_back(arr[start]);
	comb(arr, combs, cur, start + 1, targetSize - 1, n);

	// arr[start]를 포함하지 않는 경우
	cur.pop_back();
	comb(arr, combs, cur, start + 1, targetSize, n);
}

vector<vector <int>> getCombs(vector<int> &arr, int &n) {
	vector<vector<int>> combs; // final result

	vector<int> cur;
	comb(arr, combs, cur, 0, LOTTO_TARGET_SIZE, n);

	return combs;
}

int main(void) {
	while (true) {
		/* 입력 */
		int n; cin >> n;
		if (n==0) break;

		vector<int> arr;
		for (int i = 0; i < n; i++) {
			int t; cin >> t;
			arr.push_back(t);
		}

		/* 조합 */
		vector<vector<int>> combs = getCombs(arr, n);

		/* 출력 */
		for (int i = 0; i < combs.size(); i++) {
			for (int j = 0; j < 6; j++) {
				cout << combs[i][j] << ' ';
			}
			cout << '\n';
		}

		cout << '\n'; // 테스트 케이스 사이 빈 줄
	}	

	return 0;
}