(c++)백준 6603번: 로또

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

6603번: 로또

[풀이]

k개의 수로 구성된 집합 S에서 6개의 수를 고르는 모든 방법을 구하는 문제이다.

고르는 수는 중복되지 않고, 순서를 바꾸는 경우는 세지 않으므로 조합을 구하면 된다.

 

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

int k;
vector<int>S(13);//집합 S
bool check[50];//선택한 숫자 true

//조합 구하기
void getSet(int idx, int cnt) {
	if (cnt == 6) {
		for (int i = 1; i <= 49; i++) {
			if (check[i] == true)
				cout << i << ' ';
		}
		cout << '\n';
		return;
	}

	for (int i = idx; i < k; i++) {
		if (check[S[i]] == true)continue;
		check[S[i]] = true;
		getSet(i, cnt + 1);
		check[S[i]] = false;
	}
}

void solution() {
	while (1) {
		cin >> k;
		//종료 조건
		if (k == 0)
			break;
		for (int i = 0; i < k; i++) {
			cin >> S[i];
		}
		getSet(0, 0);
		cout << '\n';
	}
}

int main() {
	solution();
	return 0;
}