这里用回溯法实现了 栈的出栈情况的遍历 。虽然这个题有更好的做法，但是你如果用回溯法做这道题，做完后一定会对回溯法有这更高境界的领悟，而且在整个设计算法，debug算法的过程中会感受到一种酣畅淋漓的快感。因为这个题看似很小，其实规模很大，要考虑方方面面的问题，很多很多。
上题。
输入一个序列 比如 123。你进栈的顺序必须是按照这个序列来，但是你可以这样，进1，然后在2进入前，把1出栈。所以出栈顺序就有了许多种可能。
我讲一下我一开始是怎么做的：
感觉这题很简单，直接开始码代码，发现有新的需求，直接改，一处改，处处改，bug比比皆是，而且怎么改都是错的，因为思路上就有了偏差。
正确的做法是怎样的：
做回溯法和其他的不一样，对逻辑的缜密和条理性要求更高，特别是碰到大规模的题目的时候。所以你应该做的第一件事，是，打开一个txt文档，写下你的思路。
接下来你只需要把你的文字转化成代码就可以了。由于我的思路是写给我自己看的，所以我这里重新写一下思路分析。
1.你的输入队列是1,2,3。所以我3推进去之后，后面就再也没有进栈的操作了，因为没有已经元素已经推光了，所以只需要进行出栈操作就可以了，所以这里进行统一处理。分两类情况，一，元素推光。二，元素还未推光。
2.元素未推光的情况。这里又分两种情况。当前栈是空的，当前栈是非空的。栈空，只能直接入栈（因为你元素未推光，所以肯定可以进行入栈操作）。栈非空。
3.栈非空的时候其实又有两种情况，你可以选择入栈（因为你元素未推光，所以肯定可以进行入栈操作），也可以选择出栈（栈非空）。所以我们用一个for循环，第一次执行入栈操作，当回溯回来的时候，for循环到下一个，执行出栈操作。
这样就把思路完美的分析出来了。接下来我会每一步都贴上对应的代码。
元素推光的一类情况
if (level == length) { // TODO: 2017/11/19 这里执行的是：把当前记录的出栈情况数组添加到所有情况的二维数组里，最后一起输出level == length。这里的level是我当前的层级。我什么都没入栈。level是0。每入栈一个数字，会执行递归，参数是level + 1。
length是数组的长度。这里是3。你的level是从0开始到，如果想到3，就已经加了4次。所以说这是一种元素都推光的情形。
元素未推光的一类情况-当前栈是空的
if (list.size() == 0) { list.add(inOrder[level]); back(level + 1, index); list.remove(list.size() - 1); }我这里的list是模拟的栈。栈是空的，只能入栈，所以add，然后level+1进行回溯，进入下一层。这里的index先不用管，没有影响的。当你back(level + 1, index);执行完以后，你后面的层级的所有情况都已经搞定了，所以你这里需要把你推的东西重新移除，进行另外方向的寻找同时又避免你推进去的东西影响另外的判断，因为你和另外的情况是平行的，如果你不删除这个数的话你这次操作就影响了另外的情况，会出错。所以这里是必须移除的。
元素未推光的一类情况-当前栈非空的
for (int i = 0; i < 2; i++) { if (i == 0) { list.add(inOrder[level]); back(level + 1, index); list.remove(list.size() - 1); } else { int num = list.remove(list.size() - 1); current[index] = num; back(level, index + 1); list.add(num); } }非空情况你可以推也可以不推，所以用了一个for循环，第一次弄入栈的情况，第二次回溯回来循环执行到下一个地方，就执行下面的代码块即出栈操作。
也是一样你添加了之后就要移除，移除了之后就要添加。这里出栈多了一个操作current[index] = num;就是记录下你的出栈情况，这个index初始是0，当你出了一次栈以后，在继续遍历的时候，就要把index + 1带进去，让后面的层级对你的出栈情况数组的接下来的一位进行分析。所以我们可以看到，如果是入栈，level + 1会被传进去，如果是出栈，index+1会被传进去，前者代表的是你的入栈队列处理到哪个位置了，后者代表的是你的出栈队列处理到哪个位置了。
这就没了。
如果说还有的话就是元素推光的那一类情况，数据又是怎么处理的。有兴趣可以看一下。
取得你所有出栈情况的二维数组的当前是第几行。这里从0,0开始向下找，找到第一个值不为0的数，就是我们要找的行数了。
int row = -1; //找到第一个没有被赋值过的行,这个找到的i就是pure(纯净，未赋值过的)行号 int flag = -1; for (int i = 0; i < 100; i++) { if (allPossible[i][0] == 0) { row = i; break; } }
把你栈中的剩下的元素记录下来（应该是要推掉的，但是为了不影响回溯的时候的数据，所以直接读出来了）
//把栈中剩余的数按出栈顺序读到结果数组里，实际上不出栈,怕影响之前的情况 for (int i = 0; i < list.size(); i ++) {//经检验，list出栈的数据完全正确！ int num = list.get(i); for (int j = length - 1; j >= 0; j --) { if (allPossible[row][j] == 0) { allPossible[row][j] = num; break; } } }
把在回溯的过程中出栈的元素也加上（因为我们这里到3就结束了简化了操作，所以需要通过这一步和上一步把出栈顺序完整拼接起来）
//把current里的结果也一并加上 for (int i = 0; i < length; i++) { if (allPossible[row][i] == 0) { allPossible[row][i] = current[i]; } else break; }
搞定了。上结果图
贴上完整回溯代码
void back(int level, int index) {//1,2带进去验证 level = 0 length = 2//最后发现index还是有必要的 if (level == length) { // TODO: 2017/11/19 这里执行的是：把当前记录的出栈情况数组添加到所有情况的二维数组里，最后一起输出 int row = -1; //找到第一个没有被赋值过的行,这个找到的i就是pure(纯净，未赋值过的)行号 int flag = -1; for (int i = 0; i < 100; i++) { if (allPossible[i][length - 1] == 0) { row = i; break; } } //把栈中剩余的数按出栈顺序读到结果数组里，实际上不出栈,怕影响之前的情况 for (int i = 0; i < list.size(); i ++) {//经检验，list出栈的数据完全正确！ int num = list.get(i); for (int j = length - 1; j >= 0; j --) { if (allPossible[row][j] == 0) { allPossible[row][j] = num; break; } } } //把current里的结果也一并加上 for (int i = 0; i < length; i++) { if (allPossible[row][i] == 0) { allPossible[row][i] = current[i]; } else break; } // for (int i = 0; i < length; i ++) {//肯定不能都置为0，不然回溯的时候会打乱前面的数据 // current[i] = 0; // } return; } else {//这里level是0到最后一层，index指代当前操作数，如果仍在这个范围内，代表数没用完 if (list.size() == 0) { list.add(inOrder[level]); back(level + 1, index); list.remove(list.size() - 1); } else { for (int i = 0; i < 2; i++) { if (i == 0) { list.add(inOrder[level]); back(level + 1, index); list.remove(list.size() - 1); } else { int num = list.remove(list.size() - 1); current[index] = num; back(level, index + 1); list.add(num); } } } } }
贴上全部代码
public class Test { int length; int[][] allPossible; String[][] allOperate; int[] current; String[] operate; int[] inOrder; // int[] outOrder; List<Integer> list;//这个当做栈 int operateIndex; Test(int... ints) {//123321,后面3个是要求的出栈顺序，可以不用理会 //length = ints.length / 2; length = ints.length; allPossible = new int[100][length];//不想分析有几种可能，暂定100行 allOperate = new String[100][length * 2]; current = new int[length]; operate = new String[length * 2]; inOrder = new int[length]; for (int i = 0; i < length; i++) { inOrder[i] = ints[i]; } // outOrder = new int[length]; // for (int i = 0; i < length; i++) { // outOrder[i] = ints[i + length]; // } list = new ArrayList<>(); operateIndex = 0; } void back(int level, int index) {//1,2带进去验证 level = 0 length = 2//最后发现index还是有必要的 if (level == length) { // TODO: 2017/11/19 这里执行的是：把当前记录的出栈情况数组添加到所有情况的二维数组里，最后一起输出 int row = -1; //找到第一个没有被赋值过的行,这个找到的i就是pure(纯净，未赋值过的)行号 int flag = -1; for (int i = 0; i < 100; i++) { if (allPossible[i][length - 1] == 0) { row = i; break; } } //把栈中剩余的数按出栈顺序读到结果数组里，实际上不出栈,怕影响之前的情况 for (int i = 0; i < list.size(); i ++) {//经检验，list出栈的数据完全正确！ int num = list.get(i); for (int j = length - 1; j >= 0; j --) { if (allPossible[row][j] == 0) { allPossible[row][j] = num; break; } } } //把current里的结果也一并加上 for (int i = 0; i < length; i++) { if (allPossible[row][i] == 0) { allPossible[row][i] = current[i]; } else break; } // for (int i = 0; i < length; i ++) {//肯定不能都置为0，不然回溯的时候会打乱前面的数据 // current[i] = 0; // } return; } else {//这里level是0到最后一层，index指代当前操作数，如果仍在这个范围内，代表数没用完 if (list.size() == 0) { list.add(inOrder[level]); back(level + 1, index); list.remove(list.size() - 1); } else { for (int i = 0; i < 2; i++) { if (i == 0) { list.add(inOrder[level]); back(level + 1, index); list.remove(list.size() - 1); } else { int num = list.remove(list.size() - 1); current[index] = num; back(level, index + 1); list.add(num); } } } } } void print() { int row = -1; for (int i = 0; i < 100; i++) { if (allPossible[i][0] == 0) { row = i; break; } } for (int i = 0; i < row; i++) { for (int j = 0; j < length; j++) { System.out.print(allPossible[i][j] + " "); } System.out.println(); } } public static void main(String[] args) throws Exception { Test test = new Test(1, 2, 3); test.back(0, 0); test.print(); } }
懂的人会发现自己的回溯法已经大成了，夸张点的甚至感觉自己的逻辑思维都清晰了许多。