백준 6603 로또 (c++/백트래킹)

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

처음 푼 방문여부 배열로 체크하며 검사한 풀이

출력 조건만 보고 오름차순 조건과 방문여부 배열을 추가했지만

입력 조건에 원소가 오름차순으로 주어진다는 것을 확인하고 하단에 풀이를 추가

#include<iostream>
#include<map>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
using namespace std;
int arrsize;
int arr[13];
int prarr[13];
bool check[13];
void back(int prev, int size);
int main()
{
	cin >> arrsize;
	while (arrsize != 0)
	{
		memset(check, 0, sizeof(check));
		for (int i = 0; i < arrsize; i++)
		{
			cin >> arr[i];
		}
		back(-1,0);
		cout << "\n";
		cin >> arrsize;
	}
}
void back(int prev,int size)
{
	if (size == 6) {
		for (int i = 0; i < size; i++)
		{
			cout << prarr[i] << " ";
		}
		cout << "\n";
		return;
	}
	for (int i = 0; i < arrsize; i++)
	{
		if (!check[i] && arr[i]>prev)
		{
			prarr[size] = arr[i];
			check[i] = 1;
			back(arr[i],size + 1);
			check[i] = 0;
		}
	}
	
}

 

더 간단하게 풀 수 있다.

#include<iostream>
#include<map>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
using namespace std;
int arrsize;
int arr[13];
int prarr[13];
bool check[13];
void back(int prev, int size);
int main()
{
	cin >> arrsize;
	while (arrsize != 0)
	{
		memset(check, 0, sizeof(check));
		for (int i = 0; i < arrsize; i++)
		{
			cin >> arr[i];
		}
		back(0,0);
		cout << "\n";
		cin >> arrsize;
	}
}
void back(int start,int size)
{
	if (size == 6) {
		for (int i = 0; i < size; i++)
		{
			cout << prarr[i] << " ";
		}
		cout << "\n";
		return;
	}
	for (int i = start; i < arrsize; i++)
	{
			prarr[size] = arr[i];
			back(i+1,size + 1);
	}
	
}