题解 | #火车进站#
火车进站
https://www.nowcoder.com/practice/97ba57c35e9f4749826dc3befaeae109
import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int num = in.nextInt(); int[] trains = new int[num]; for(int i = 0; i < num; i++){ trains[i] = in.nextInt(); } in.close(); List<String> res = new ArrayList<>(); Stack<Integer> station = new Stack<>(); dfs(res,"",trains,station,0,0); Collections.sort(res); for(String s : res){ System.out.println(s); } } private static void dfs(List<String> res,String tmp, int[] trains, Stack<Integer> station, int in, int out){ if(out == trains.length){ //所有火车均已出站 res.add(tmp); } if(!station.empty()){ //车站不空,尚有火车没有出站 int train = station.pop(); dfs(res,tmp + train + " ",trains,station,in,out + 1); station.push(train); } if(in < trains.length){ //还有火车没有进站 station.push(trains[in]); dfs(res,tmp,trains,station,in + 1,out); station.pop(); } } }