c++ 백준_15666_"N과 M(12)"

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

15666번: N과 M (12)

 

​

중복 제거를 위해

string과 set을 활용하려 했다.

​

근데 string을 사용하니

1 11 1111 111 과 같을 때 잘 돌아가지 않았다.

​

그래서 vector 와

중복 방지를 위한 set을 활용하여 해결하였다.

 

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

int N, M;
int number[8];
set<vector<int>> st;

void DFS(int depth, int idx, vector<int> result) {

	if (depth == M) {

		if (st.find(result) != st.end())
			return;
		st.insert(result);

		for (int i = 0; i < M; i++) {
			cout << result[i] << " ";
		}
		cout << "\n";
		return;
	}

	for (int i = idx; i < N; i++) {
		result.push_back(number[i]);
		DFS(depth + 1,i , result);
		result.pop_back();
	}

}

int main(void) {

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);


	cin >> N >> M;


	for (int i = 0; i < N; i++) {
		cin >> number[i];
	}

	sort(number, number + N);

	vector<int> result;
	DFS(0,0, result);

}