给定入栈顺序求所有出栈顺序：java递归

笔试和手撕都遇到类似题目，没做出来追悔莫及记录一下

如输入 abc，输出

cba

bca

bac

acb

abc

可以回溯但是太麻烦了，换一种思路，每一步操作，可以选择入栈，或者出栈，只要满足条件，就可以继续递归，直到所有字符都出栈即可打印

import java.util.Scanner;


public class OutputStack {
//	思路：每个时刻，当前栈都有两种选择，继续入栈，或者出栈。因此，用递归就可以实现了。
    static void all_order(String in,String stack,String out){
        if(in.length()==0&&stack.length()==0){
            System.out.println(out);
        }
        if(in.length()!=0){
           all_order(in.substring(1),stack+in.charAt(0),out);
        }
        if(stack.length()!=0){
            all_order(in,stack.substring(0,stack.length()-1),out+stack.charAt(stack.length()-1));
        }
    }
    public static void main(String[] args) {
    	Scanner input = new Scanner(System.in);
		String a=input.nextLine();
        all_order(a,"","");
    }
}

对于固定步，每步固定选择的题都可以套这个模板，比如输出可能得括号匹配

给定一个数字n，输出所有可能的括号匹配，如

2

()()

(())

也是一样的套路