AcWing 842. 配列数(C++アルゴリズム)

AcWing 842. すうじをならべる
1、テーマ:整数nを与え、数字1~nを一列に並べると、いろいろな並び方があります.
今、辞書順にすべての並べ替え方法を出力してください.
入力フォーマットは、整数nを含む1行です.
出力フォーマットは、すべての配列スキームを辞書順に出力し、各スキームが1行を占めます.
データ範囲1≦n≦7
入力サンプル:3出力サンプル:1 2 3 1 3 2 2 1 3 3 3 1 3 1 3 1 2 3 2 1
2、基本思想:再帰して、辞書の順序に従って1組(3級、例えば1 2 3)を並べ終わるたびに、前の級に遡って前の級の並ぶ数を確定する.stateでのシフト演算を繰り返すのを避けるために、すでにデータがある位置をマークします.
3、C++コードは以下の通りである(このコードはAcWingサイトコードを参照する)

#include 

using namespace std;

const int N = 10;

int path[N];
int n, state;

void dfs(int u, int state)
{
     
    if (u == n)
    {
     
        for (int i = 0; i < n; i ++ ) cout << path[i] << ' ';
        cout << endl;
    }
    
    for (int i = 0; i < n; i ++ )//①     ②             
    {
     
        if (!(state >> i & 1))//   i      
        {
     
            path[u] = i + 1;
            dfs(u + 1, state + (1 << i));//①           ②            
        }
    }
}

int main()
{
     
    cin >> n;
    
    dfs(0, 0);
    
    return 0;
}//     AcWing    

注意:各レイヤの再帰でstateの値は変更されていません.