ZJGSU 1850 不同出栈情况

描述

假设有n个元素依次进栈，给出他们可能的不同的出栈情况。

输入

3

1 2 3

输出

1 2 3

1 3 2

2 1 3

2 3 1

3 2 1

输入样例 1  

3
1 2 3

输出样例 1

1 2 3
1 3 2
2 1 3
2 3 1
3 2 1

#include <stdio.h>

int tot, res, sta, n;
int r[2005], s[2005];

void recall(int m) {
	if (m == n + 1) { // 若所有元素都入过栈，输出当前出栈序列
		tot++;
		for (int i = 1; i <= res; i++) {
			printf("%d ", r[i]);
		}
		for (int i = sta; i > 1; i--) {
			printf("%d ", s[i]);
		}
		printf("%d\n",s[1]);
		return;
	}
	if (sta > 0) {
		r[++res] = s[sta];
		sta--;
		recall(m); // 栈顶元素出栈
		s[++sta] = r[res];
		res--; // 回溯操作
	}
	s[++sta] = m; // 当前元素入栈
	recall(m + 1);
	sta--; // 回溯操作
}

int main() {
	scanf("%d", &n);
	int a;
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a);
	}
	tot = 0;
	res = 0;
	sta = 0;
	recall(1);
	return 0;
}