题解 | #火车进站#

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

const int sz = 12;
int n;
int in[sz];
int ind_i;
int stk[sz];
int ind_s;
int out[sz];
int ind_o;
char res[5000][sz];
int cnt;
int comp(const void* a, const void* b) {
    return strcmp(a, b);
}
void dfs() {
    if(ind_o == n) {
        int i;
        for(i = 0; i < ind_o; ++i) res[cnt][i] = out[i] +'0';
        res[cnt++][i] = '\0';
        return;
    }
    if(ind_i < n) {
        stk[ind_s++] = in[ind_i++];
        dfs();
        --ind_s, --ind_i;
    }
    if(ind_s) {
        out[ind_o++] = stk[--ind_s];
        dfs();
        stk[ind_s++] = out[--ind_o];
    }
}
int main() {
    while (scanf("%d", &n) == 1) {
        for(int i = 0; i < n; ++i) scanf("%d", in + i);
        ind_i = ind_o = ind_s = cnt = 0;
        dfs();
        qsort(res, cnt, sizeof(res[0]), comp);
        for(int i = 0; i < cnt; ++i) {
            for(int j = 0; j < n; ++j) printf("%c ", res[i][j]);
            putchar('\n');
        }
    }
    return 0;
}