백준 15666번: N과 M (12) (C++)

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

 

15666번: N과 M (12)

사용했던 숫자를 여러 번 사용할 수 있다.

 

따라서 숫자 사용 여부를 관리하는 배열이 필요하지 않다.

 

수열을 벡터에 쌓고, 원하는 길이만큼 쌓이면 set에 넣고 벡터를 비워주는 것을 반복한다.

 

set에는 중복되는 원소가 들어갈 수 없다는 것을 활용했다.

 

 

 

#include<iostream>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;
int m, n, num[8], arr[8], Start;
set<vector<int> > st;
void func(int k) {
	if (k == m) {
		vector<int> v;
		for (int i = 0; i < m; i++)
			v.push_back(arr[i]);
		st.insert(v);
		v.clear();
		return;
	}
	if (k == 0) Start = 0;
	for (int i = Start; i < n; i++) {
		arr[k] = num[i];
		Start = i;
		func(k + 1);
	}

}
int main(void) {
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> num[i];
	sort(num, num + n);
	func(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;
}