题解 | #火车进站#

#include<stdio.h>
#include<string.h>

int num;
int train[15]={0};
int train2[15]={0};
int b[15]={0};
int v[15]={0};

int check()
{
    int stack[15];
    int size=0;
    int index=0;
    for(int i=0;i<num;i++)
    {
        stack[size++]=train2[i];
        while(size>0&&stack[size-1]==b[index])
        {
            size--;
            index++;
        }
    }
    if(size==0){return 1;}
    else{return 0;}
    return 0;
}
void dfs1(int i)
{
    if(i>=num)
    {
        if(check())
        {
           for(int m=0;m<num;m++)
            {
                printf("%d ",b[m]);
            }
            printf("\n"); 
        }
        return;
    }
    for(int j=0;j<num;j++)
    {
        if(v[j]==0)
        {
            v[j]=1;
            b[i]=train[j];
            dfs1(i+1);
            v[j]=0;
        }
    }
    return;
}

int main(void)
{
   scanf("%d",&num);
    for(int i=0;i<num;i++)
    {
        scanf("%d",&train2[i]);
    }
    for(int i=0;i<num;i++)
    {
        train[i]=i+1;
    }
    //用dfs1计算全排列
    dfs1(0);
    
    return 0;
}