java 回溯法

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner s=new Scanner(System.in);
        while(s.hasNext()){
           s.nextLine();
           String[] arr = s.nextLine().split(" ");
           List<List<String>> list = new ArrayList<>();
           huisu(0, arr, new Stack<>(), new ArrayList<>(), list);
           list.sort((o1, o2) -> {
            int iTemp = 0;
            for (int i = 0; i < o1.size(); i++) {
                if (o1.get(i).compareTo(o2.get(i)) != 0) {
                    iTemp = i;
                    break;
                }
            }
            return o1.get(iTemp).compareTo(o2.get(iTemp));
        });
           list.forEach(o-> System.out.println(String.join(" ",o)));
        }
    }

    private static void huisu(int start, String[] arr, Stack<String> stack, List<String> listTemp, List<List<String>> list) {
        if (start == arr.length) {
            if (!stack.isEmpty()) {
                String peek = stack.peek();
                listTemp.add(peek);
                stack.pop();
                huisu(start, arr, stack, listTemp, list);
                stack.push(peek);//回溯
                listTemp.remove(listTemp.size() - 1);//回溯
            } else {
                list.add(new ArrayList<>(listTemp));
            }
            return;
        }
        ///////可入可出的情况
        //入栈
        stack.push(arr[start]);
        huisu(start + 1, arr, stack, listTemp, list);
        stack.pop();
        //出栈
        if (!stack.isEmpty()) {
            String peek = stack.peek();
            stack.pop();
            listTemp.add(peek);
            huisu(start, arr, stack, listTemp, list);
            listTemp.remove(listTemp.size() - 1);//回溯
            stack.push(peek);//回溯
        }
    }
}