[C++] 백준 15657번: N과 M (8)

아이디어

그냥 백트랙킹... 중복 없애고... 중복 조합....

풀이

수열을 입력받고 오름차순으로 정렬한 뒤에 중복된 항목을 제거한다.

백트랙킹을 통해 중본 조합을 구한다.

출력한다. 끝.

코드

#include <bits/stdc++.h>

using namespace std;

#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 EL "\n"

int N, M;
vector<int> arr, ret;
vector<vector<int>> ans;

void dfs(int cursor) {
	if (ret.size() == M) {
		ans.push_back(ret);
		return;
	}
	for(int i = cursor; i < N; ++i) {
		ret.push_back(arr[i]);
		dfs(i);
		ret.pop_back();
	}
}

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

	cin >> N >> M;

	arr = vector<int>(N);
	FOR(i, N)
		cin >> arr[i];

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

	int i = 1;
	while (true) {
		if (i >= arr.size()) break;
		if (arr[i] == arr[i - 1]) arr.erase(arr.begin() + i);
		else ++i;
	}

	N = arr.size();
	dfs(0);

	for (auto& el : ans) {
		for (auto& num : el)
			cout << num << " ";
		cout << EL;
	}

	return 0;
}