# 【ZJ】e446. Arrangement Generation

## [題目連結](https://zerojudge.tw/ShowProblem?problemid=e446)

## **時間複雜度**

* $O(N!)$

## **解題想法**

這題一看完題目就很明顯可以看出他是一題枚舉裸題，實作上可以直接用 C++ 提供的 STL 函式 [next_permutation](https://cplusplus.com/reference/algorithm/next_permutation/) 下去實作，但是我這在寫這題的時候就想說練一下自己對枚舉的熟悉度，所以我選擇用**遞迴**下去實作，詳細程式如下

## **完整程式**

這邊有一個比較需要注意的地方就是這題如果單單只用 cin / cout 配簡單 IO 優化的話是會吃 <span style="color:orange">**TLE**</span> 的（我猜應該是卡 n = 10 的測資），所以在處理這題的時候要記得特別把 cin / cout 改成 scanf / printf 他才會 <span style="color:green">**AC**</span>

/* Question : ZeroJudge e446. Arrangement Generation */

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

#define opt ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mem(x, value) memset(x, value, sizeof(x));
#define maxint 0x3F
#define pii pair<int, int>
#define pdd pair<double, double>
#define f first
#define s second

const auto dir = vector< pair<int, int> > { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
const int MAXN = 10 + 50;
const int Mod = 1e9 + 7;
int n, ans[MAXN];
bool visited[MAXN];

void nextPermutation( int level ){
    if( level == n+1 ){
        for( int i = 1 ; i <= n ; i++ ) printf("%d ", ans[i]);
        printf("\n");
        return;
    }

    for( int i = 1 ; i <= n ; i++ ){
        if( visited[i] == true ) continue;
        visited[i] = true;
        ans[level] = i;
        nextPermutation(level+1);
        visited[i] = false;
    }
}

signed main(){
    opt;
    mem(visited, false);
    scanf("%d", &n);
    nextPermutation(1);
}