[BOJ] 백준 6603번 로또 C++

문제

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

6603번: 로또

풀이

일반적인 백트래킹 문제이다.

n개 중에서 m개를 뽑는 조합이라고 가정하였을때 n은 각 tc마다 바뀌는 vector의 크기가 되고, m은 6개로 고정이다. 이를 바탕으로 조합을 돌려 모든 경우의 수를 출력하면 된다. lotto와 isused를 초기화하는 것을 잊지말자.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

vector<int> lotto;
bool isused[14];

void reset()
{
	memset(isused, false, sizeof(isused));
	lotto.clear();
}

void func(int idx, int cnt)
{
	if (cnt == 6)
	{
		for (int i = 0; i < lotto.size(); i++)
		{
			if (isused[i])
			{
				cout << lotto[i] << " ";
			}
		}
		cout << "\n";
		return;
	}

	for (int i = idx; i < lotto.size(); i++)
	{
		if (!isused[i])
		{
			isused[i] = true;
			func(i + 1, cnt + 1);
			isused[i] = false;
		}
	}
}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(0);

	while (true)
	{
		int size;
		cin >> size;

		if (size == 0)
		{
			return 0;
		}

		for (int i = 0; i < size; i++)
		{
			int a;
			cin >> a;
			lotto.push_back(a);
		}

		func(0, 0);
		cout << "\n";

		reset();
	}
}