[BOJ] 15469 - N 과 M (1)

문제 : https://www.acmicpc.net/problem/15649

---

[알고리즘풀이]

중복을 허락하지 않으면서 모든 경우를 뽑아야 하므로, 방문한 지점을 체크하는 배열을 활용한 백트레킹 기법으로 문제를 해결한다.

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

int n, m;
bool visited[9];
vector<int> v;
void bt(int);

int main(void) {
	cin >> n >> m;
	bt(0);
}

void bt(int cnt) {
	if (cnt == m) {
		for (int i = 0; i < m; i++)
			cout << v[i] << ' ';
		cout << '\n';
		return;
	}
	for (int i = 1; i <= n; i++) {
		if(!visited[i]){
			visited[i] = true;
			v.push_back(i);
			bt(cnt + 1);
			visited[i] = false;
			v.pop_back();
		}
	}
}

---