C 解法, 执行用时: 4ms, 内存消耗: 348KB, 提交时间: 2021-01-17

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_N 10
int idx;
char N, M, arr[MAX_N], push_stk[MAX_N], idx_push, pop_arr[MAX_N], idx_pop, opt[8888][MAX_N+1], **opt_p;
void DG(char k)
{
	if(k==N){
		char i = idx_pop, j = idx_push;
		memcpy(opt[++idx], pop_arr, (++i)*sizeof(char));
		for( ; j!=-1; opt[idx][i++] = push_stk[j--]) ;
		opt[idx][i] = '\0';
		return ;
	}
	if(idx_push != -1){
		pop_arr[++idx_pop] = push_stk[idx_push--];
		DG(k);
		push_stk[++idx_push] = pop_arr[idx_pop--];
	}
	push_stk[++idx_push] = arr[k];
	DG(k+1);
	idx_push--;
}
void DG_quick_sort(int start, int end)
{
	if(start < end){
		int i = start, j = end;
		char *p_tmp = opt_p[start];
		
		while(i < j)
		{
			while(i<j && strcmp(opt_p[j], p_tmp)>=0) j--;
			opt_p[i] = opt_p[j];
			
			while(i<j && strcmp(opt_p[i], p_tmp)<=0) i++;
			opt_p[j] = opt_p[i];
		}
		opt_p[i] = p_tmp;
		
		DG_quick_sort(start, i-1);
		DG_quick_sort(i+1, end);
	}
}
int main(void)
{
	int i;   char j;
	for( ; scanf("%d", &N)!=EOF; ){
		for(i=0; i<N; i++){
            getchar();
			scanf("%c", arr+i);
        }
		M = N-1;
		
		push_stk[0] = arr[0];
		idx_push = 0;   idx_pop = idx = -1;
		DG(1);
		
		opt_p = (char **)malloc( (idx+1)*sizeof(char *) );
		for(i=0; i<=idx; i++)
			opt_p[i] = opt[i];
		DG_quick_sort(0, idx);
		for(i=0; i<=idx; i++){
			for(j=0; j<M; j++)
				printf("%c ", opt_p[i][j]);
			printf("%c\n", opt_p[i][j]);
		}
		free( opt_p );
	}
	return 0;
}

C 解法, 执行用时: 4ms, 内存消耗: 360KB, 提交时间: 2021-01-24

#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(void){
    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(void){
    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;
}