백준 15663 N과 M (9) (C++)

15663번: N과 M (9)

백트래킹을 이용한 문제이다. 이전 문제와의 차이점이라면 이미 출력한 수열과 같은 값을 가지는 수열은 다시 출력을 하지 않는다는 점이다. 이부분을 set을 이용하여 풀어보았다. 쉽게 풀 수 있었던 문제였다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

int N, M;
vector<int> v;
vector<int> tmp;
set<vector<int>> result;
bool check[8];

void dfs() {
	if (tmp.size() == M) {
		result.insert(tmp);
		return;
	}

	for (int i = 0; i < v.size(); i++) {
		if (check[i]) continue;

		check[i] = true;
		tmp.push_back(v[i]);
		dfs();
		check[i] = false;
		tmp.pop_back();
	}
}

void solution() {
	sort(v.begin(), v.end());
	dfs();

	for (auto elem : result) {
		for (int i = 0; i < elem.size(); i++) {
			cout << elem[i] << " ";
		}
		cout << "\n";
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N >> M;

	int a;
	for (int i = 0; i < N; i++) {
		cin >> a;
		v.push_back(a);
	}

	solution();
	
	return 0;
}