#include <iostream>

using namespace std;

int n, cnt = 1;
int a[10];
bool st[10];

void dfs(int i)
{
    if(i > n)
    {
        for(int j = 1; j <= n; j++) cout << a[j] << " ";
        cout << endl;
        return;  //  递归终点返回
    }

    for(int j = 1; j <= n; j++)
    {
        if(!st[j]) 
        {
            st[j] = true;
            a[i] = j;
            dfs(i + 1);
            st[j] = false;  //  恢复现场
        }
    }

}


int main()
{
    cin >> n;

    dfs(1);

    return 0;
}

第二种 加快速度

#include <iostream>

using namespace std;

int n, cnt = 1;
int a[10];
bool st[10];

void dfs(int i)
{
    if(i > n)
    {
        for(int j = 1; j <= n; j++) printf("%d ", a[j]);
        printf("\n");
        return;  //  递归终点返回
    }

    for(int j = 1; j <= n; j++)
    {
        if(!st[j]) 
        {
            st[j] = true;
            a[i] = j;
            dfs(i + 1);
            st[j] = false;  //  恢复现场
        }
    }

}


int main()
{
    scanf("%d", &n);

    dfs(1);

    return 0;
}