[BJ] 15649 - N과 M(1) (백트레킹 기초)

 

백트레킹은 모든 경우의 수를 재귀적으로 탐색할떄 사용한다.

for문으로도 가능하지만 n개의 숫자가 늘어날수록 중첩for문을 해야하니 효율적이지 못할 수 있다.

 

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

int n, m;

bool vis[15];
vector<int> v;

void dfs()
{
	if (v.size() == m)
	{
		for (const int& i : v)
		{
			cout << i << ' ';
		}

		cout << '\n';
	}

	for (int i = 1; i <= n; ++i)
	{
		if (!vis[i])
		{
			vis[i] = true;
			v.push_back(i);
			dfs();
			vis[i] = false;
			v.pop_back();
		}
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	
	dfs();

	return 0;
}