[백준]15663_N과 M(9), 15664_N과 M(10)

https://www.acmicpc.net/problem/15663
https://www.acmicpc.net/problem/15664

Solved

✔ 알고리즘 분류: 백트래킹

✔ N과 M(9): N개의 자연수 중에서 M개를 고른 수열을 모두 구하기. 중복되는 수열은 여러번 출력하면 안된다.
⏩ 기본적인 백트래킹을 사용한 조합. 중복은 set을 이용하여 처리

✔ N과 M(10):
N개의 자연수 중에서 M개를 고른 수열. 중복되는 수열은 여러번 출력하면 안된다.
고른 수열은 비내림차순이어야 한다.
(비내림차순: 길이가 $K$인 수열 $A$가 $A_{1}$

N과 M(9), N과 M(10) 기본 set

using namespace std;
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <string>

int n, m;
vector<int> v;
int arr[9];
bool visit[9];
set<string> st;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	int x;
	for (int i = 0; i < n; i++) {
		cin >> x;
		v.push_back(x);
	}
	bool simpleV = true;
	for (int i = 1; i < n; i++) {
		if (v[i - 1] != v[i]) {
			simpleV = false;
			break;
		}
	}
	if (simpleV == false) {
		sort(v.begin(), v.end());
		comb(0);
	}
	else {
		for (int i = 0; i < m; i++)
			cout << v[i] << ' ';
	}
}

N과 M(9)

void comb(int cnt) {
	if (cnt == m) {
		string s = "";
		for (int i = 0; i < m; i++)
			s += to_string(arr[i]) + ' ';
		if (st.find(s) == st.end()) {
			st.insert(s);
			cout << s << '\n';
		}
		return;
	}
	for (int i = 0; i < n; i++) {
		if (!visit[i]) {
			visit[i] = true;
			arr[cnt] = v[i];
			comb(cnt + 1);
			visit[i] = false;
		}
	}
}

N과 M(10)

void comb(int idx, int cnt) {
	if (cnt == m) {
		string s = "";
		for (int i = 0; i < m; i++)
			s += to_string(arr[i]) + ' ';
		if (st.find(s) == st.end()) {
			st.insert(s);
			cout << s << '\n';
		}
		return;
	}
	for (int i = idx; i < n; i++) {
		if (!visit[i]) {
			visit[i] = true;
			arr[cnt] = v[i];
			comb(i+1, cnt + 1);
			visit[i] = false;
		}
	}
}