题解 | #火车进站#

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int arr[10] = { 0 };
int out[10] = { 0 };
int in[10] = { 0 };
int res[6000][10] = { 0 };
int pos = 0;
int cmp(const void*l1,const void*l2)
{
    return memcmp((int(*)[10])l1,(int(*)[10])l2,40);
}
void dfs(int in_num, int out_num, int N_num, int N)
{
    if (out_num == N)
    {
        memcpy(res[pos], out, sizeof(out));
        pos++;
        return;
    }
    if (N_num<N)
    {
        in[++in_num] = arr[N_num++];
        dfs(in_num, out_num, N_num, N);
        in_num--;
        N_num--;
    }
    if (in_num >= 0)
    {
        out[out_num++] = in[in_num--];
        dfs(in_num, out_num, N_num, N);
        in[in_num++] = out[out_num--];
    }
}
int main() {
    int N=0;
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &arr[i]);
    }
    dfs(-1, 0, 0, N);
    qsort(res,pos,sizeof(res[0]),cmp);
    for (int i = 0; i <pos; i++)
    {
        for (int j = 0; j < N; j++)
        {
            printf("%d ", res[i][j]);
        }
        printf("\n");
    }
    return 0;
}