[백준 15649/c++] N과 M (1)

백트래킹을 사용하여 푸는 첫 문제이다

백트래킹이란 이전 결과를 보존하고 그 이전 결과를 기반으로 재귀를 사용하여 경우의 수를 찾는 방법이다

백트래킹은 브루트 포스 = 완전 탐색 과는 조금 다른데,

브루트 포스의 경우 개별적인 경우를 반복문을 통해 모든 경우를 구한다면

백트래킹은 이전 결과를 기반으로 재귀를 통해 가지치기 하여 경우의 수를 찾는 방법이다

n과 m을 전역 변수로 주어 백트래킹 함수의 인자를 줄였고,

아직 초보라 백트래킹의 패턴을 따라 만들어서 다른 블로그 답들과 비슷한 코드가 나왔다

아직 사용에 익숙하지 않으니 더 많이 풀고 이해하여 내 것으로 만들자

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

15649번: N과 M (1)

#include <bits/stdc++.h>
using namespace std;

int n, m;
int ar[10];
bool isused[10];

void bt(int k){
	if (k == m)
	{
		for (int i = 0; i < m; i++)
		{
			cout << ar[i] << " ";
		}
		cout << "\n";
		return;
	}
	
	for (int i = 1; i <= n; i++)
	{
		if (!isused[i])
		{
			ar[k] = i;
			isused[i] = true;
			bt(k + 1);
			isused[i] = false;
		}
	}
}
	
int main(){
	ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	
	cin >> n >> m;
	bt(0);
	
	return 0;
}