[백준] 6603번: 로또

6603번: 로또

 

dfs로 모든 순열을 출력할수 있도록 해주는 대신 사전순으로 출력이 되어야하기 떄문에 순열배열 arr에

arr.back()<num[i]로 항상 오름차순이 될 수있도록 했다.

 

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#define MAX 50
using namespace std;

vector<int>num;

void dfs(int size, int now, vector<int>arr,vector<int>visit) {
	if (size < now) {
		for (int i = 0;i < size;i++) {
			cout << arr[i] << ' ';
		}
		cout << '\n';
		return;
	}

	for (int i = 0;i < num.size();i++) {
		if (!visit[i]) {
			if (arr.size()==0||arr.back() < num[i]) {
				visit[i] = true;
				arr.push_back(num[i]);
				dfs(size, now + 1, arr, visit);
				visit[i] = false;
				arr.pop_back();
			}
		}
	}
}

int main() {

	while (1) {
		int n;
		cin >> n;

		if (n == 0) break;
		
		for (int i = 0,t=0;i < n;i++) {
			cin >> t;
			num.push_back(t);
		}

		sort(num.begin(), num.end());
		dfs(6, 1, vector<int>(), vector<int>(MAX,0));
		num.clear();

		cout << '\n';
	}

}