15654번: N과 M (5)

🥅 문제

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

 

🔍 설계

전형적인 백트래킹 문제이다. 사전 순으로 출력해야 하므로, 오름차순 정렬 후, 백트래킹을 사용하면 된다.

 

👊 풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;
vector<int> number(8);
vector<bool> visited(8);
vector<int> temp;

void bt(int count) {
	if (count == m) {
		for (int i = 0; i < m; i++) {
			cout << temp[i] << " ";
		}
		cout << "\n";
	}
	for (int i = 0; i < n; i++) {
		if (!visited[i]) {
			visited[i] = true;
			temp.push_back(number[i]);
			bt(count + 1);
			temp.pop_back();
			visited[i] = false;
		}
	}
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> number[i];
	}
	sort(number.begin(), number.begin() + n);
	
	bt(0);
	
	return 0;
}