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

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

15663번: N과 M (9)

이 문제는 조합 만드는 유형의 시리즈 중 한 문제인 것 같다. 재귀함수를 이용하여 간단하게 풀 수 있었다. 입력되는 숫자 중 중복되는 것에 대해서는 map<int, int>를 활용하여 해당 숫자의 갯수를 저장했다. vector<int>에 출력할 숫자들을 하나씩 넣어가며 그 크기가 M이 됐을 때 출력하는 방식으로 코드를 작성했다.

#include <bits/stdc++.h>

using namespace std;

#define TC(T) int T; cin >> T; while(T--)
#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define INF 987654321
#define ERR 1e-13
#define EL "\n"
#define VI vector<int>
#define VVI vector<VI>
#define VVVI vector<VVI>

int N, M;
map<int, int> numbers;
vector<int> ans;
void combination(int step) {
	if (step == M) {
		for (auto& el : ans) {
			cout << el << ' ';
		}
		cout << EL;
		return;
	}
	for (auto& remain : numbers) {
		if (remain.second > 0) {
			remain.second--;
			ans.push_back(remain.first);
			combination(step + 1);
			ans.pop_back();
			remain.second++;
		}
	}
}

int main() {
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	FAST_IO;

	cin >> N >> M;

	FOR(i, N) {
		int number;
		cin >> number;
		numbers[number]++;
	}

	combination(0);

	return 0;
}