[백준 15649] N과 M(1) 순열

가장 기본적인 순열문제임

백트래킹으로 풀면 된다

 

123 213 이 다르므로 

DFS안에서 무조건 첨부터 끝까지 돌게 하면 된다

 

 

---

#include <iostream>
#include <vector>
#define SIZE 11

using namespace std;

bool visited[SIZE];
int arr[SIZE];
vector<int> ans;

int N, M;

void print() {
	for (int i = 0; i < M; i++) cout << ans[i] << " ";
	cout << "\n";
}

void DFS(int cnt) {
	if (cnt == M) {
		print();
		return;
	}

	for (int i = 1; i <= N; i++) {
		if (!visited[i]) {
			visited[i] = true;
			ans.push_back(arr[i]);
			DFS(cnt + 1);
			ans.pop_back();
			visited[i] = false;
		}
	}
	return;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N >> M;
	for (int i = 1; i <= N; i++) arr[i] = i;

	DFS(0);
	return 0;
}