题解 | #火车进站#

同时存在两种可能的情况时，递归实现需要在每一种情况递归出来后，做好回溯处理。

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

int N;
int train[10] = {0};
int in_train[10] = {0};
int out_train[10] = {0};
char res[60000][10] = {0};
int kind = 0;

int cmp(void *a, void *b)
{
    return strcmp((char *)a, (char *)b); 
}

void DFS(int in_num, int out_num, int index)
{
    if (out_num == N) {
        for (int i = 0; i < N; i++) {
            res[kind][i] = out_train[i] + '0';
        }
        kind++;
        //printf("RETURN: in_num=%d, out_num=%d, index=%d, kind=%d\n", in_num, out_num, index, kind);
        return;
    }
    
    // 进站
    if (index < N) {
        in_train[++in_num] = train[index++];
        //printf("IN: in_num=%d, out_num=%d, index=%d, in=%d\n", in_num, out_num, index, in_train[in_num - 1]);
        DFS(in_num, out_num, index);
        in_num--;
        index--;
    }
    
    // 出站
    if (in_num >= 0) {
        out_train[out_num++] = in_train[in_num--];
        //printf("OUT: in_num=%d, out_num=%d, index=%d, out=%d\n", in_num, out_num, index, in_train[in_num + 1]);
        DFS(in_num, out_num, index);
        in_train[++in_num] = out_train[--out_num];
    }
}

int main(void)
{
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%d", &train[i]);
    }
    
    DFS(-1, 0, 0);
    
    qsort(res, kind, sizeof(res[0]), cmp);
    
    //printf("%d\n", kind);
    for (int i = 0; i < kind; i++) {
        for (int j = 0; j < N; j++) {
            printf("%c ", res[i][j]);
        }
        printf("\n");
    }
    
    return 0;
}