[백준15649] N과 M (C++)

BOJ 바로가기

풀이

숫자가 이전에 나온 적 있는지 확인할 수 있도록 bool형 check 배열을 만들어두는 것이 핵심이다. 숫자를 배열에 넣을 때마다 check배열을 false로 만들어주고, 재귀함수를 돌린 후에는 다시 true로 바꾸어주어야 한다.

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

int ans[9];
bool check[9];

void go(int idx, int n, int m)
{
	if (idx > m)
	{
		for (int i = 1; i <= m; i++)
		{
			cout << ans[i];
			if (i != m)
				cout << ' ';
			else
			{
				cout << '\n';
				return;
			}
		}
	}
	for (int i = 1; i <= n; i++)
	{
		if (check[i] == true)
		{
			ans[idx] = i;
			check[i] = false;
			go(idx + 1, n, m);
			check[i] = true; // ✨
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, m; cin >> n; cin >> m;
	for (int i = 1; i <= n; i++)
		check[i] = true;
	go(1, n ,m);
}