백준 15649번: N과 M (1)

[문제 링크]

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

---

간단한 백트래킹 문제였다.

이전에 담은 숫자를 중복으로 담지 않기 위해 vector<bool>에 담은 숫자를 마킹하는 방식을 사용하였다.

기저사례는 vector<int> 크기가 M과 같아지는 경우로 설정하였고,

기저사례에 도달할 경우 재귀를 수행하지 않고 vector에 담긴 원소를 출력하는 방식으로 구현하였다.

---

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

int N, M;

void backtracking(vector<int>& backpack, vector<bool>& picked)
{
	if (backpack.size() == M)
	{
		for (auto a : backpack)
		{
			cout << a << ' ';
		}
		cout << '\n';

		return;
	}
	
	for (int i = 1; i <= N; i++)
	{
		if (picked[i]) continue;

		backpack.push_back(i);
		picked[i] = true;
		backtracking(backpack, picked);
		backpack.pop_back();
		picked[i] = false;
	}
}

int main(void)
{
	cin >> N >> M;

	vector<int> backpack;
	vector<bool> picked(N+1, false);
	backtracking(backpack, picked);

	return 0;
}