BaekJoon 15655번: N과 M(6)

풀이법

1) 재귀 함수를 이용하여 level에 도달하게 되면 출력하는 형식으로 BackTracking을 구현한다.

2) 초기 배열을 오름차순으로 정리한다.

3) 현재 설정된 배열의 마지막 index 값을 라스트로 두어서 이보다 새로운 값이 작을 경우 continue 한다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, m;
vector<int> vec;
int arr[9];
bool visited[10001];
void backtracking(int level, int last)
{
	if (level == m)
	{
		for (int i = 0; i < m; i++)
		{
			cout << arr[i] << " ";
		}
		cout << "\n";
		return;
	}
	for (int i = 0; i < vec.size(); i++)
	{
		if (visited[vec[i]])
		{
			continue;
		}
		if (last > vec[i])
		{
			continue;
		}
		visited[vec[i]] = true;
		arr[level] = vec[i];
		backtracking(level+1, arr[level]);
		visited[vec[i]] = false;
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		vec.push_back(a);
	}
	sort(vec.begin(), vec.end());
	backtracking(0, 0);
}

github.com/pearlcrum/CodingTest/tree/main

pearlcrum/CodingTest