백준 15665번: N과 M (11) (C++)

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

15665번: N과 M (11)

 

숫자의 입력이 중복되어서 들어올 수 있다.

 

결과로 나오는 수열은 오름차순으로 정렬되는 상태여야 한다. 하지만 입력은 정렬되어서 들어오는 것이 아니기 때문에 입력을 모두 받은 이후에 오름차순 정렬을 해줘야 한다.

 

또한, 사용했던 숫자를 재사용할 수 있기 때문에 숫자의 사용 중 여부를 판단하는 배열 또한 필요하지 않다.

 

그리고 수열이 중복되어서 생성될 수 있는데, 이는 중복을 허용하지 않는 set을 활용해서 처리했다.

 

#include<iostream>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;
int m, n, arr[7], num[7];
set<vector<int > > st;
vector<int> v;
void func(int k) {
	if (k == m) {
		for (int i = 0; i < m; i++) {
			v.push_back(arr[i]);
		}
		st.insert(v);
		v.clear();
		return;
	}
	for (int i = 0; i < n; i++) {
		arr[k] = num[i];
		func(k + 1);
	}
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> num[i];
	sort(num, num + 1);
	func(0); //0번까지 채워져있다
	set<vector<int> >::iterator itr;
	for (itr = st.begin(); itr != st.end(); itr++) {
		vector<int> tmp = *itr;
		for (int i = 0; i < tmp.size(); i++)
			cout << tmp[i] << ' ';
		cout << '\n';
	}
	return 0;
}