描述

假设有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;
}