[BOJ - 15666] N과 M(12)

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

15666번: N과 M (12)

 

중복된 값을 허용하지 않은 중복 조합 문제 입니다.

 

풀이 방법은 중복 조합을 먼저 구현하고 N과 M(11)과 비슷한 방식으로 풀었습니다.

 

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

using namespace std;

int n, m;
vector<int> vec, sel;
map<string, int> dict;

void dfs(int node) {
	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 = node; i < vec.size(); i++) {
		sel.push_back(vec[i]);
		dfs(i);
		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(0);

	getchar();
	getchar();

	return 0;
}