백준 15666번 N과 M (12) C++

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

 

일반적인 백트래킹으로 문제를 해결하였는데, 비내림차순이고 중복이 아닌 것들만 출력하였다.

 

#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;

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 (ans.empty() || ans.back() <= v[i]) {
			ans.push_back(v[i]);
			dp(v, cnt + 1, ans);
			ans.pop_back();
		}
	}
}

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);
};