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

출처 : https://www.acmicpc.net/problem/15663

 

일반적인 백트래킹 문제인데, 중복을 포함하지 않게 하기 위해 string 타입의 set을 이용해서 중복된 숫자는 출력하지 않았다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>

using namespace std;
using ll = long long;

vector<bool> found(8, false);
set<string> strs;
int n, m;

void dp(const vector<int>& v, int cnt, vector<int> &ans) {
	if (cnt >= m) {
		string str = "";
		for (auto a : ans) {
			str += to_string(a) + " ";
		}
		if (strs.find(str) == strs.end()) {
			strs.insert(str);
			cout << str << "\n";
		}
		return;
	}
	for (int i = 0; i < v.size(); i++) {
		if (found[i]) continue;
		found[i] = true;
		ans.push_back(v[i]);
		dp(v, cnt + 1, ans);
		ans.pop_back();
		found[i] = false;
	}
}

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

	cin >> n >> m;
	vector<int> v(n);
	vector<int> ans;
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	sort(v.begin(), v.end());
	dp(v, 0, ans);
};