BaekJoon 6603번: 로또(C++)

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

6603번: 로또

풀이법

1) 전형적인 백트래킹 문제였다.

2) 현재 값 보다 큰 index를 이용해서 경우의 수를 탐색했으며, cnt가 6에 도달하게 되면 현재까지의 값을 출력하는 방식으로 문제를 해결할 수 있었다.

3) 재귀와 백트래킹이 익숙하지 않은 분들은 소스코드를 보며 이해하심을 추천드린다.

#include <string>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int n;
int arr[14];
int ans[14];
bool visited[14];
void backtracking(int index, int cnt)
{
	if (cnt == 6)
	{
		for (int i = 1; i <= cnt; i++)
			cout << ans[i] << " ";
		cout << "\n";
		return;
	}
	for (int i = index + 1; i <= n; i++)
	{
		if (!visited[i])
		{
			visited[i] = true;
			ans[cnt + 1] = arr[i];
			backtracking(i, cnt + 1);
			visited[i] = false;
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n;
	while (n != 0) {
		for (int i = 1; i <= n; i++)
			cin >> arr[i];
		backtracking(0, 0);
		cout << "\n";
		cin >> n;
	}
}