题解 | #火车进站#

当还有火车还未进站时,可以选择进站;
当站中有火车时,可以选择让最外面的火车出站;
二者互不影响;
可以使用回溯算法来进行模拟:

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextInt()){
            //思路:如果栈中有元素就可以选择是否弹出,如果还有火车未进站,就可以选择进站,二者互不影响
            int n = sc.nextInt();
            List<Integer> list = new ArrayList<>();
            List<List<Integer>> res = new ArrayList<>();
            Deque<Integer> stack = new LinkedList<>();
            int[] nums = new int[n];
            for(int i=0;i<n;i++){
                nums[i] = sc.nextInt();
            }
            //StringBuilder sb = new StringBuilder();
            dfs(stack,nums,0,list,res);
            Set<String> set = new TreeSet<>();
            for(List<Integer> ls : res){
                StringBuilder sb = new StringBuilder();
                for(Integer i : ls){
                    sb.append(i+" ");
                }
                set.add(sb.toString());
            }
            for(String s : set){
                System.out.println(s);
            }
        }
    }
    public static void dfs(Deque<Integer> stack,int[] nums,int m,List<Integer> list,List<List<Integer>> res){
        if(m==nums.length && stack.isEmpty()){
            //将一条记录添加到集合中
            List<Integer> tmp = new ArrayList<>(list);
            res.add(tmp);
            return;
        }
        //如果还有火车尚未入栈,可以入栈
        if(m<nums.length){
            stack.push(nums[m]);
            dfs(stack,nums,m+1,list,res);
            //回溯
            stack.pop();
        }
        //如果栈中有元素可以出栈
        if(!stack.isEmpty()){
            int a = stack.pop();
            list.add(a);
            dfs(stack,nums,m,list,res);
            //回溯
            stack.push(a);
            list.remove(list.size()-1);
        }
    }
}