백준 Silver 3 N과 M 5

N과 M (백준 Silver 3)

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

가능한 수열의 조합을 출력하는 문제이다
재귀(백트래킹)를 통해 풀 수 있으며
어제 푼 백트래킹 문제보다 난이도가 낮았기에
비교적 쉽게 풀 수 있었다

해결 방식?

원래는 현재까지 출력한 횟수를 count로 담고
m에서 빼주려 하였으나
수열이 잘 출력되지 않았다
(나름대로 ‘가지치기’를 시도한?)

헌데 곰곰히 생각해 보니
출력은 ‘마지막’인 count == m 에서만
진행하면 더 깔끔하게 수열이 출력되었고
이미 ‘수열’이 완성된 상황에서만 출력하니
딱히 가지치기를 할 필요가 없었다

그렇기에 set을 통해
인덱스 중복만 검사하고
vector로 수열을 저장한 뒤
마지막에 출력해주는 것으로 통과하였다

제출한 코드

#include<iostream>
#include<vector>
#include<unordered_set>
#include<algorithm>

using namespace std;

void recur(const vector<int>& nums, vector<int>& selected,unordered_set<int>& selectIdx,int m)
{
	int count = selected.size();
	if (count == m)
	{
		for (int v : selected)
			cout << v << ' ';
		cout << '\n';
		return;
	}

	for (int i = 0; i < nums.size(); i++)
	{
		if (selectIdx.find(i) != selectIdx.end())
			continue;

		selected.push_back(nums[i]);
		selectIdx.insert(i);
		recur(nums, selected, selectIdx, m);
		selected.pop_back();
		selectIdx.erase(i);
	}
}

int main()
{
	int n, m;
	cin >> n >> m;

	vector<int> vec(n);

	for (int i = 0; i < n; i++)
	{
		int t;
		cin >> t;
		vec[i] = t;
	}

	sort(vec.begin(), vec.end());
	vector<int> selected;
	unordered_set<int> selectIdx;
	recur(vec, selected, selectIdx, m);

	return 0;
}