[Baekjoon] 15666번: N과 M (12)

🥅 문제

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

 

🔍 설계

같은 수를 여러 번 사용해도 되므로, 수를 저장할 때 여러 개를 저장할 필요가 없으므로 중복을 제거한다. 중복을 제거하기 전에 오름차순 정렬이 이루어지므로, 비내림차순으로 결과를 출력할 준비가 되었다.

 

중복을 허용하므로 방문 처리는 필요가 없고, 비내림차순이므로 마지막으로 사용한 인덱스부터 이후까지 사용할 수 있다.

 

👊 풀이

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

int n, m, temp;
vector<int> number;
vector<int> result;

void bt(int count, int last_idx) {
	if (count == m) {
		for (int i = 0; i < m; i++) {
			cout << result[i] << " ";
		}
		cout << "\n";
		return;
	}

	for (int i = last_idx; i < n; i++) {
		result.push_back(number[i]);
		bt(count + 1, i);
		result.pop_back();
	}
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> temp;
		number.push_back(temp);
	}
	
	sort(number.begin(), number.end());
	number.erase(unique(number.begin(), number.end()), number.end());
	n = number.size();

	bt(0, 0);
	
	return 0;
}