[BOJ - 15663] N과 M(9)

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

15663번: N과 M (9)

 

순열인데 중복되는 것들을 제외하여 값을 출력하는 문제 입니다.

 

n개에서 m개를 선택했을 때 최초의 경우로 생성된 값일 경우 출력하고

 

이미 출력된 적이 있을 경우 그냥 넘겨주기만 하면 됩니다.

 

문제는 기존에 생성된 값인지 아닌지 여부를 판단하는 것인데 저는 map을 사용했습니다.

 

나머지는 백트래킹으로 순열을 구현해서 어려움은 없었습니다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <string>

using namespace std;

int n, m;
int visited[9];
vector<int> vec, sel;
map<string, int> dict;

void dfs() {

	if (sel.size() == m) {

		string temp;
		for (int i = 0; i < sel.size(); i++) {
			temp += to_string(sel[i]);
		}

		if (temp == "") return;
		if (dict[temp] != 0) return;
		else {
			dict[temp] += 1;
			for (int i = 0; i < sel.size(); i++) {
				printf("%d ", sel[i]);
			}
			printf("\n");
		}

		return;
	}

	for (int i = 0; i < vec.size(); i++) {
		if (visited[i] == 0) {
			visited[i] = 1;
			sel.push_back(vec[i]);
			dfs();
			visited[i] = 0;
			sel.pop_back();
		}
	}
}

int main(void) {

	scanf("%d %d", &n, &m);

	for (int temp, i = 0; i < n; i++) {
		scanf("%d", &temp);
		vec.push_back(temp);
	}

	sort(vec.begin(), vec.end());

	dfs();

	getchar();
	getchar();

	return 0;
}