[BOJ] 15649 N과 M (1) C++

개요

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

15649번: N과 M (1)

실버급 백트래킹 문제다.

풀이

배열을 재귀로 탐색하다 조건이 맞으면(수열의 길이가 M이 됐을 때) 리턴시켜줬다.

방문이 끝나면 다른 경우의 수에서도 인덱스를 방문 할 수 있도록 방문 배열을 다시 false 시켜주어야 한다.

코드

#include<iostream>
#include<algorithm>
using namespace std;
constexpr int LIMIT = 10;

int N, M;
int num[LIMIT];
bool visited[LIMIT];

void slove(int cnt)
{
	if (cnt > M)
	{
		for (int i = 1; i <= M; i++)
			cout << num[i] << " ";
		cout << "\n";
		return;
	}

	for (int i = 1; i <= N; i++)
	{
		if (visited[i]) continue;
		visited[i] = true;
		num[cnt] = i;
		slove(cnt+1);
		visited[i] = false;
	}
}

int main()
{
	cin.tie(0)->sync_with_stdio(0);

	cin >> N >> M;
	slove(1);
}