https://www.acmicpc.net/problem/10974
백트래킹을 이용하였다.
이미 수열에 포함한 숫자는 다시 넣을 수 없도록 is_used 배열로 중복을 관리해주었다.
#include <iostream>
#include <vector>
using namespace std;
int n;
vector<int> arr;
vector<bool> is_used;
void backtracking(int len) {
if(len == n) {
for(auto& e : arr) {
cout << e << " ";
}
cout << "\n";
return;
}
for(int i=1; i<=n; i++) {
if(is_used[i]) continue;
arr[len] = i;
is_used[i] = true;
backtracking(len + 1);
is_used[i] = false;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
arr.resize(n);
is_used.resize(n, false);
backtracking(0);
return 0;
}