深信服24届秋招算法：所有可能的出栈顺序-526互联

public class Main {
    private static final Scanner in = new Scanner(System.in);
    public static void main(String[] args) throws UnsupportedEncodingException {
        //echo();
        String s = "abcdef";
        char [] seq = s.toCharArray();
        boolean [] visited = new boolean[seq.length];
        List<Character> res = new ArrayList<>();
        List<List<Character>> ans = new LinkedList<>();
        Stack<Character> stk = new Stack<>();
        bt(seq, visited, res, ans, stk);
        for (List<Character> cs : ans){
            for(char c : cs){
                System.out.print(c);
            } System.out.println();
        }

    }
    static void bt(char [] seq, boolean [] visited, List<Character> res, List<List<Character>> ans, Stack<Character> stk){
        if(res.size() == seq.length){
            // 在这里验证 是否是可行出栈顺序
            for(int i = 0, j = 0; i < seq.length; i++){
                stk.push(seq[i]);
                while(!stk.isEmpty() && stk.peek() == res.get(j)){
                    stk.pop();
                    j++;
                }
            }
            if(stk.isEmpty())
                ans.add(new ArrayList<>(res));
            stk.clear();
            return;
        }
        for(int i = 0; i < seq.length; i++){
            if(visited[i]) continue;
            visited[i] = false;
            res.add(seq[i]);

            bt(seq, visited, res, ans, stk);

            visited[i] = false;
            res.remove(res.size() - 1);
        }
    }
}